Luyện tập #2

Trong phòng thí nghiệm nano, các nhà khoa học đang nghiên cứu một quy trình tổng hợp vật chất mang tên "nhân hai cộng một". Quy trình này biến đổi một cấu trúc vật chất (được mô tả bằng một xâu ký tự \(a\)) theo nguyên tắc sau:

1. Nhân đôi: Tạo ra một bản sao của xâu \(a\) và gắn vào ngay sau xâu gốc (thu được \(a + a\)).
2. Cộng một: Gắn thêm một nguyên tử mới (là một ký tự \(c\) bất kỳ trong bảng chữ cái) vào cuối xâu vừa tạo.

Ví dụ: Từ xâu ab, quy trình sẽ tạo ra ab + ab + x = ababx.

Mọi cấu trúc đều bắt đầu từ "hư không" (xâu rỗng). Nhà nghiên cứu An vừa tìm thấy một số mẫu vật lạ và muốn kiểm tra nguồn gốc của chúng. Với mỗi mẫu vật (xâu \(s\)), An có hai loại câu hỏi:

• Loại 1: Xâu \(s\) này có phải là kết quả thuần túy của quy trình trên (xuất phát từ xâu rỗng) hay không?
• Loại 2: Nếu ta được phép sắp xếp lại vị trí các nguyên tử trong \(s\) tùy ý, liệu có thể tạo ra một cấu trúc đúng chuẩn quy trình trên (có thể được tạo từ xâu rỗng) hay không?

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 10\)) là số lượng mẫu vật cần kiểm tra.
• \(T\) dòng tiếp theo, mỗi dòng chứa thông tin về một mẫu vật gồm:
  • Một xâu ký tự \(s\) chỉ gồm các chữ cái in thường (độ dài không quá \(270\,000\) ký tự).
  • Một số nguyên \(\theta \in \{1, 2\}\) biểu thị loại câu hỏi (\(\theta = 1\) là hỏi Loại 1, \(\theta = 2\) là hỏi Loại 2).

Output

• Với mỗi mẫu vật, in ra YES nếu câu trả lời là có thể, hoặc NO nếu không thể.

Example

4
a 1
aab 1
aba 1
aba 2

YES
YES
NO
YES

Subtask

• Subtask 1: \(30\%\) số điểm có độ dài xâu \(s \le 3\) và \(\theta = 1\).
• Subtask 2: \(20\%\) số điểm khác có \(\theta = 1\).
• Subtask 3: \(30\%\) số điểm khác có độ dài xâu \(s \le 3\).
• Subtask 4: \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Tại trung tâm nghiên cứu AI, có hai robot thám hiểm Alpha và Beta đang cần nạp năng lượng. Hệ thống sạc bao gồm các trạm năng lượng nằm trên một trục thẳng, tổng cộng có \(2 \times n\) trạm sạc. Mỗi trạm sạc cung cấp một loại năng lượng thuộc cấp độ từ \(1\) đến \(n\).

Để kích hoạt hệ thống tối thượng, cả Alpha và Beta đều phải lần lượt thu thập đủ bộ năng lượng từ cấp \(1\) đến cấp \(n\) theo đúng thứ tự (tức là phải có cấp \(i - 1\) mới được nạp cấp \(i\)).

Hệ thống vận hành theo quy tắc như sau:

• Ban đầu, hệ thống sẽ đưa hai robot đến vị trí của trạm năng lượng cấp \(1\) gần nhất (chi phí di chuyển ban đầu này được coi là \(0\) hoặc đã được tính toán trong khâu chuẩn bị, không tính vào kết quả).
• Mỗi trạm sạc chỉ phục vụ được cho một robot duy nhất.
• Khoảng cách giữa hai trạm liền kề là \(1\) đơn vị.
• Mục tiêu là điều khiển hai robot di chuyển từ các trạm cấp \(i\) sang các trạm cấp \(i + 1\) sao cho tổng quãng đường cả hai đi được là nhỏ nhất.

Hệ thống đôi khi gặp sự cố và đảo vị trí các trạm sạc cho nhau. Với mỗi thay đổi đó, bạn hãy tính toán lại tổng quãng đường tối ưu.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) (\(1 \le n, q \le 2 \cdot 10^5\)).
• Dòng tiếp theo gồm \(2 \times n\) số nguyên dương \(a_1, a_2, \dots, a_{2n}\) (\(1 \le a_i \le n\)) là cấp độ năng lượng tại các trạm. Dữ liệu đảm bảo mỗi cấp độ xuất hiện đúng 2 lần.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(i, j\) (\(1 \le i < j \le 2n\)) mô tả sự cố hoán đổi trạm sạc ở vị trí \(i\) và \(j\).

Output

• Với mỗi truy vấn hoán đổi, in ra tổng quãng đường nhỏ nhất tìm được.

Example

3 2
1 1 2 2 3 3
2 3
1 4

7
12

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n, q \le 6\).
• Subtask 2 (\(20\%\) số điểm): \(n, q \le 16\).
• Subtask 3 (\(20\%\) số điểm): \(n, q \le 200\).
• Subtask 4 (\(20\%\) số điểm): \(n, q \le 2000\).
• Subtask 5 (\(20\%\) số điểm): không có giới hạn gì thêm.

Với hai xâu \(a\) và \(b\), Alice có thể gộp hai xâu thành một xâu \(c\) theo quy tắc sau:

• Ban đầu xâu \(c\) rỗng.
• Alice lấy ký tự đầu tiên của \(a\) nối vào cuối xâu \(c\).
• Alice lấy ký tự đầu tiên của \(b\) nối vào cuối xâu \(c\).
• Alice lấy ký tự thứ hai (nếu có) của \(a\) nối vào cuối xâu \(c\).
• Alice lấy ký tự thứ hai (nếu có) của \(b\) nối vào cuối xâu \(c\).
• ...
• Alice lấy ký tự cuối cùng của xâu \(a\) hoặc \(b\) nối vào cuối xâu \(c\).

Ví dụ, Alice có thể gộp hai xâu "ab" và "cdef" thành "acbdef". Lưu ý rằng thứ tự của các xâu trong thao tác gộp là quan trọng, chẳng hạn Alice có thể gộp hai xâu "cdef" và "ab" thành "cadbef".

Trên bảng đang có \(n\) xâu \(s_1, s_2, ..., s_n\) từ trái sang phải. Alice thực hiện \(n-1\) hành động. Với hành động thứ \(i\), cô lấy hai xâu \(s_{u_i}\) và \(s_{v_i}\) đang có trên bảng, gộp hai xâu để tạo thành xâu \(s_{n+i}\) và viết nó lên bảng, sau đó xóa hai xâu \(s_{u_i}\) và \(s_{v_i}\). Alice muốn biết sau khi mình thực hiện tất cả các hành động thì xâu cuối cùng còn lại là xâu nào.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 10^5)\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_i\) chỉ gồm các ký tự trong bảng chữ cái tiếng Anh in thường. Dữ liệu đảm bảo tổng độ dài các xâu \(s_i\) không vượt quá \(2 \cdot 10^6\)
• \(n-1\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên dương \(u_i, v_i\) \((1 \leq u_i, v_i \leq n+i)\). Dữ liệu đảm bảo hai xâu \(s_{u_i}\) và \(s_{v_i}\) vẫn chưa bị xóa khỏi bảng trước hành động thứ \(i\)

Output

• Một dòng duy nhất gồm xâu cuối cùng còn lại trên bảng.

Example

3
abc
de
fgh
1 3
2 4

daefbgch

Scoring

• \(20\%\) số điểm có \(n = 2\)
• \(20\%\) số điểm khác có \(n \leq 1000\) và tổng độ dài các xâu \(s_i\) không quá \(5000\)
• \(30\%\) số điểm khác có trong tất cả các xâu \(s_i\) có đúng một ký tự "b", còn lại là ký tự "a"
• \(30\%\) số điểm còn lại không có giới hạn gì thêm