12 - 10 - 2026

Những người bạn thân lâu năm có thể sử dụng một loại ký hiệu khác thường để xác nhận và trò chuyện với nhau, gọi là mật mã huynh đệ. Tuấn và Tú chơi thân với nhau từ nhỏ, và họ đã nghĩ ra mật mã cho riêng mình. Theo đó, mỗi người sẽ chọn ra một xâu gồm \(n\) ký tự, mỗi ký tự đều thuộc tập {{, [, (, }, ], )}. Khi gặp mặt, họ sẽ đem xâu của mình trộn lẫn vào nhau, lần lượt là ký tự đầu tiên trong xâu của Tuấn, rồi đến ký tự đầu tiên trong xâu của Tú, tiếp theo là ký tự thứ hai, và cứ thế. Nếu xâu thu được là dãy ngoặc đúng độ dài \(2n\), độ sâu \(k\) thì mật mã được xác nhận. Dãy ngoặc đúng được định nghĩa như sau:

• Xâu rỗng là dãy ngoặc đúng bậc \(0\)
• Nếu \(A\) là dãy ngoặc đúng bậc \(a\), \(B\) là dãy ngoặc đúng bậc \(b\) thì: {A}, (A), [A] là các dãy ngoặc đúng bậc \(a + 1\). \(AB\) là dãy ngoặc đúng bậc \(\max(a, b)\)

Trải qua thời gian, Tuấn không còn nhớ rõ xâu mà ngày đó mình đã chọn. Trong trí nhớ của Tuấn, xâu của anh sẽ trông giống như: ?(??]?{}. Còn xâu của Tú thì dĩ nhiên là anh không nhớ gì. Tuấn thắc mắc là có bao nhiêu khả năng có thể có của mật mã huynh đệ, tức là có bao nhiêu dãy ngoặc đúng độ dài \(2n\) độ sâu \(k\) sao cho các vị trí không phải dấu ? trên xâu của Tuấn sau khi trộn lại đều trùng khớp trên dãy ngoặc đó.

Input

• Dòng đầu chứa hai số nguyên dương: \(n\), \(k\).
• Dòng thứ hai chứa một xâu có độ dài \(n\), gồm các ký tự thuộc tập {{, [, (, }, ], ), ?}.

Output

• Ghi số cách khôi phục tìm được, sau khi chia lấy dư cho \(10^9 + 7\).

Example

8 3
?(??]?{}

4617

2 1
(?

3

Scoring

• \(1 \le k \le n \le 1000\)
• Subtask \(1\) (\(20\%\) số điểm): \(n \le 50\)
• Subtask \(2\) (\(20\%\) số điểm): \(k \le 5\)
• Subtask \(3\) (\(60\%\) số điểm): Ràng buộc gốc

Trên sân khấu có \(2N\) ca sĩ đứng thành một hàng. Mỗi ca sĩ hát bè cao (A) hoặc bè trầm (B). Thông tin cho bởi xâu \(S\) độ dài \(2N\): ca sĩ thứ \(i\) (từ phải sân khấu) hát bè cao nếu kí tự thứ \(i\) của \(S\) là A, hát bè trầm nếu là B. Có đúng \(N\) kí tự A và \(N\) kí tự B.

Các ca sĩ sẽ trình bày \(K\) bài. Mỗi ca sĩ hát đúng một bài. Với mỗi bài cần thoả:

• Có ít nhất một ca sĩ hát bài đó.
• Số ca sĩ bè cao bằng số ca sĩ bè trầm.
• Các ca sĩ hát bài đó đứng cạnh nhau.
• Trong các ca sĩ hát bài đó, mọi ca sĩ bè cao đứng bên phải sân khấu so với mọi ca sĩ bè trầm.

Nhạc trưởng có thể đổi chỗ hai ca sĩ kề nhau nhiều lần để tồn tại cách phân bài thoả mãn. Hãy tính số thao tác đổi chỗ ít nhất.

Input

• Dòng 1: hai số nguyên \(N\) và \(K\).
• Dòng 2: xâu \(S\) độ dài \(2N\).

Output

• In một dòng: số thao tác đổi chỗ kề nhau ít nhất.

Example

1 1
BA

1

7 5
ABBAAABBABABBA

3

Ràng buộc

• \(1 \leq N \leq 5\,000\)
• \(1 \leq K \leq N\)
• \(S\) có đúng \(N\) kí tự A và \(N\) kí tự B.

Subtask

• Subtask \(1\) (\(20\) điểm): \(N \leq 50\).
• Subtask \(2\) (\(30\) điểm): \(N \leq 500\).
• Subtask \(3\) (\(50\) điểm): không có ràng buộc bổ sung.

Với mỗi câu đố cho hai số nguyên \(a\) và \(b\), hãy tìm số nguyên dương \(p\) thỏa \(p^3 + a\cdot p = b\). Nếu không có \(p\) như vậy, in NIE.

Input

• Dòng đầu tiên chứa số câu đố \(T\).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(0 \le a \le 10^9\), \(1 \le b \le 10^{18}\)).

Output

• Với mỗi câu đố, in ra \(p\) (số nguyên dương duy nhất nếu có) hoặc NIE.

Example

3
3 14
7 10
2 12

2
NIE
2

Ràng buộc

• \(1 \le T \le 10^5\)
• \(0 \le a \le 10^9\)
• \(1 \le b \le 10^{18}\)

Subtask

• Một nhóm \(100\) điểm.

Đây là một bài toán tương tác (interactive). Hùng được giao nhiệm vụ sắp xếp lại sách trong một thư viện theo độ dày của sách. Có \(n\) quyển sách với chiều dày khác nhau đôi một. Có \(n\) ô đựng sách, được đánh số từ \(1\) đến \(n\), mỗi ô đựng đúng một quyển. Tiếc thay, khi nhận nhiệm vụ, Hùng đang không có mặt ở đó; nên cậu sẽ trao đổi thư từ với nhân viên ở thư viện để thực hiện nhiệm vụ của mình.

Mỗi lần gửi thư, Hùng sẽ gửi một danh sách gồm các cặp chỉ số: \((i_1, j_1), (i_2, j_2), (i_3, j_3), \dots, (i_k, j_k)\) với ý định so sánh độ dày của các cặp quyển sách ở các ô đó. Độ dài của lá thư là \(k\) phải không quá \(n/2\), và mỗi chỉ số xuất hiện nhiều nhất một lần trong một lá thư. Tức là các số \(i_1, j_1, i_2, j_2, \dots, i_k, j_k\) phải đôi một phân biệt.

Tuy nhiên, thư viện có hai nhân viên (tạm gọi là \(A\) và \(B\)) và mỗi người lại hiểu mệnh lệnh theo một cách khác nhau. Nhân viên \(A\) xem thư trước, đọc lần lượt từng cặp. Khi đọc đến một cặp trong danh sách, anh ta được lựa chọn là sẽ đổi chỗ hai cuốn sách trong cùng cặp đó, hoặc là không. Có nghĩa là, anh ta sẽ chọn ra một số cặp \((i_t, j_t)\) nào đó, rồi đổi chỗ quyển sách ở ô \(i_t\) cho quyển sách ở ô \(j_t\). Việc chọn những cặp nào để đổi, những cặp nào giữ nguyên là hoàn toàn do nhân viên \(A\) quyết định, không theo một quy tắc cụ thể nào. Lưu ý là nội dung của lá thư không bị \(A\) thay đổi, \(A\) chỉ đổi chỗ sách trên kệ mà thôi.

Sau khi \(A\) hết ca, sẽ tới ca làm của \(B\). Nhân viên \(B\) đọc thư và tiến hành so sánh độ dày các cặp quyển sách, sau đó gửi kết quả cho Hùng. Cứ mỗi cặp \((i_t, j_t)\), \(B\) sẽ tới nhìn vào ô \(i_t\) và \(j_t\) rồi ghi lại \(1\) hoặc \(0\) tương ứng là quyển sách ở ô \(i_t\) dày hơn hay mỏng hơn quyển sách ở ô \(j_t\).

Nhiệm vụ của Hùng là gửi không quá \(Q\) lá thư tới thư viện, để cuối cùng anh có thể đưa ra một thứ tự các ô sao cho độ dày các quyển sách theo thứ tự đó là giảm dần.

Tương tác

Để bắt đầu tương tác, bạn cần đọc vào 2 số nguyên: \(n, Q\). Quá trình tương tác diễn ra như sau:

• Để gửi thư, bạn cần in ra theo cú pháp: ASK k i1 j1 i2 j2 ... ik jk; Sau đó đọc vào một xâu nhị phân độ dài \(k\) là kết quả mà \(B\) gửi lại. Bit thứ \(t\) là \(1\) cho biết quyển sách ở ô \(i_t\) dày hơn quyển sách ở ô \(j_t\); bit \(0\) trong trường hợp ngược lại.
• Khi tìm ra thứ tự, bạn cần in ra theo cú pháp: ANSWER i1 i2 ... ik là chỉ số của các ô mà theo đó, độ dày các quyển sách là giảm dần.

Sau khi in ra một truy vấn hoặc đáp án, đừng quên xuống dòng và flush đầu ra chuẩn, nếu không bạn có thể nhận verdict Time limit exceeded. Để làm điều này, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;
• xem tài liệu chuẩn đối với các ngôn ngữ khác.

Giới hạn

• Trong tất cả các test: \(1 \leq n \leq 500\); \(500 \leq Q \leq 5000\).
• Subtask \(1\) (\(20\%\) số điểm): \(Q \geq n^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(A\) sẽ không bao giờ đổi chỗ hai cuốn sách; và \(Q \geq n \log n\).
• Subtask \(3\) (\(20\%\) số điểm): \(Q \geq n \log n\).
• Subtask \(4\) (\(20\%\) số điểm): \(A\) sẽ đổi chỗ để cuốn sách dày hơn nằm ở \(i_t\), với mọi \(t\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Ví dụ

4 50
10
0

ASK 2 1 2 3 4
ASK 1 1 4
ANSWER 4 3 1 2

Trên sân khấu có \(2N\) ca sĩ đứng thành một hàng. Mỗi ca sĩ hát bè cao (A) hoặc bè trầm (B). Thông tin cho bởi xâu \(S\) độ dài \(2N\): ca sĩ thứ \(i\) (từ phải sân khấu) hát bè cao nếu kí tự thứ \(i\) của \(S\) là A, hát bè trầm nếu là B. Có đúng \(N\) kí tự A và \(N\) kí tự B.

Các ca sĩ sẽ trình bày \(K\) bài. Mỗi ca sĩ hát đúng một bài. Với mỗi bài cần thoả:

• Có ít nhất một ca sĩ hát bài đó.
• Số ca sĩ bè cao bằng số ca sĩ bè trầm.
• Trong các ca sĩ hát bài đó, mọi ca sĩ bè cao đứng bên phải sân khấu so với mọi ca sĩ bè trầm.

Nhạc trưởng có thể đổi chỗ hai ca sĩ kề nhau nhiều lần để tồn tại cách phân bài thoả mãn. Hãy tính số thao tác đổi chỗ ít nhất.

Input

• Dòng 1: hai số nguyên \(N\) và \(K\).
• Dòng 2: xâu \(S\) độ dài \(2N\).

Output

• In một dòng: số thao tác đổi chỗ kề nhau ít nhất.

Example

1 1
BA

1

7 5
ABBAAABBABABBA

3

Ràng buộc

• \(1 \le N \le 1\,000\,000\); \(1 \le K \le N\); \(S\) có đúng \(N\) kí tự A và \(N\) kí tự B.

Subtask

• Subtask \(1\) (\(16\) điểm): \(N \le 10\).
• Subtask \(2\) (\(24\) điểm): \(N \le 500\).
• Subtask \(3\) (\(21\) điểm): \(N \le 5\,000\).
• Subtask \(4\) (\(26\) điểm): \(N \le 100\,000\).
• Subtask \(5\) (\(13\) điểm): không có ràng buộc bổ sung.