Bạn đang chơi trò chơi video hành động. Bộ điều khiển trò chơi có \(4\) phím, A, B, X và Y. Trong trò chơi này, bạn giành điểm bằng các tổ hợp nước đi. Bạn có thể thực hiện một tổ hợp nước đi bằng việc ấn các phím theo một dãy.

Trò chơi có một dãy bí mật các phím được biểu diễn bởi xâu ký tự \(S\) chỉ gồm các ký tự trong số \(4\) ký tự này. Bạn không biết xâu \(S\), nhưng biết độ dài của nó là \(N\).

Ký tự đầu tiên của \(S\) không bao giờ xuất hiện lại trong nó. Ví dụ, \(S\) có thể là ABXYY hoặc XYYAA, nhưng không thể là AAAAA hoặc BXYBX.

Bạn được ấn một dãy không quá \(4N\) phím trong một tổ hợp nước đi. Giả sử \(p\) là xâu biểu diễn dãy phím mà bạn bấm. Số điểm đạt được trong nước đi này bằng độ dài của tiền tố dài nhất của \(S\) đồng thời là xâu con của \(p\). Xâu con của một xâu \(t\) là một dãy (có thể rỗng) gồm các ký tự liên tiếp trong \(t\). Tiền tố của \(t\) là xâu con của \(t\) mà nó hoặc là xâu rỗng, hoặc bắt đầu tại ký tự đầu tiên của \(t\).

Chẳng hạn, nếu \(S\) là ABXYY và \(p\) là XXYYABYABXAY, bạn đạt \(3\) điểm vì ABX là tiền tố dài nhất của \(S\) đồng thời là xâu con của \(p\).

Nhiệm vụ của bạn là xác định xâu bí mật \(S\) bằng cách sử dụng ít tổ hợp nước đi.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

string guess_sequence(int N)

• N: độ dài của xâu \(S\).
• Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu.
• Hàm này phải trả lại xâu \(S\).

Chương trình của bạn có thể gọi hàm sau:

int press(string p)

• p: dãy các phím mà bạn bấm.
• p phải có độ dài từ \(0\) đến \(4N\), kể cả hai đầu mút. Mỗi ký tự của p phải là A, B, X hoặc Y.
• Bạn không được gọi hàm này quá \(8\,000\) lần cho mỗi bộ dữ liệu.
• Hàm này trả lại số điểm mà bạn đạt được khi ấn dãy phím biểu diễn bởi p.

Nếu một trong các điều kiện trên không được thỏa mãn, chương trình của bạn được chấm là Wrong Answer. Ngược lại, chương trình được chấm là Accepted và điểm của bạn được tính theo số lần gọi hàm press (xem phần Subtasks).

Trong C++, giao diện trong tệp combo.h của gói đính kèm là:

std::string guess_sequence(int N);
int press(std::string p);

Ví dụ

Giả sử \(S\) là ABXYY. Trình chấm gọi guess_sequence(5). Một ví dụ về trao đổi được cho trong bảng sau:

Đối với lần gọi press thứ nhất, ABX xuất hiện trong XXYYABYABXAY như một xâu con, còn ABXY thì không, nên giá trị \(3\) được trả lại.

Đối với lần gọi press thứ ba, toàn bộ ABXYY xuất hiện như một xâu con trong ABXYYABXYY, nên giá trị \(5\) được trả lại.

Đối với lần gọi press thứ sáu, không có tiền tố nào của ABXYY ngoài tiền tố rỗng xuất hiện như một xâu con trong BXYY, nên giá trị \(0\) được trả lại.

Cuối cùng, guess_sequence(5) phải trả lại ABXYY.

Tệp sample-01-in.txt trong gói nén zip đính kèm tương ứng với ví dụ này.

Hạn chế

• \(1 \le N \le 2\,000\).
• Mỗi ký tự của \(S\) là A, B, X hoặc Y.
• Ký tự đầu tiên của \(S\) không bao giờ lặp lại trong \(S\).

Trong bài toán này, trình chấm KHÔNG thích nghi. Điều đó có nghĩa là \(S\) được cố định ngay từ đầu khi chạy trình chấm và không phụ thuộc vào các truy vấn do chương trình của bạn đưa ra.

Phân nhóm

Đối với subtask \(2\), điểm cho mỗi bộ dữ liệu được tính như sau. Gọi \(q\) là số lần gọi hàm press.

Điểm của bạn cho mỗi subtask là điểm nhỏ nhất trong số các điểm của các bộ dữ liệu thuộc subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

• Dòng \(1\): \(S\).

Nếu chương trình của bạn được chấm là Accepted, trình chấm mẫu in ra Accepted: q, trong đó q là số lần gọi hàm press.

Nếu chương trình của bạn được chấm là Wrong Answer, trình chấm mẫu in ra Wrong Answer: MSG. Ý nghĩa của MSG như sau:

• invalid press: giá trị p truyền cho press không hợp lệ. Cụ thể, độ dài của p không nằm trong khoảng từ \(0\) đến \(4N\), kể cả hai đầu mút, hoặc có ký tự trong p không phải là A, B, X hay Y.
• too many moves: hàm press được gọi nhiều hơn \(8\,000\) lần.
• wrong guess: giá trị trả về của guess_sequence không trùng với xâu \(S\).

Dữ liệu vào của ví dụ trên:

ABXYY

Với đúng chuỗi \(8\) lời gọi press trong bảng ví dụ và giá trị trả về ABXYY của guess_sequence, trình chấm mẫu in ra:

Accepted: 8