Đoán vị trí trong xâu nhị phân

Đây là bài toán tương tác.

Hệ thống giữ bí mật một xâu nhị phân $s$ độ dài $n$. Xâu này chắc chắn chứa ít nhất một ký tự 0 và ít nhất một ký tự 1.

Nhiệm vụ của bạn là chỉ ra một vị trí bất kỳ chứa ký tự 0 và một vị trí bất kỳ chứa ký tự 1. Các vị trí được đánh số từ $1$ đến $n$.

Để làm điều đó, bạn được phép hỏi không quá $15$ câu hỏi. Mỗi câu hỏi là một xâu nhị phân $t$ độ dài đúng bằng $n$, và hệ thống trả lời bằng khoảng cách Hamming giữa $t$ và $s$, tức là số vị trí mà hai xâu có ký tự khác nhau.

Dữ liệu vào

Đầu tiên hệ thống in ra một dòng chứa số nguyên $n$.

Giao thức tương tác

Sau khi đọc $n$, bạn thực hiện các thao tác sau:

• Để hỏi, in ra một dòng ? t với $t$ là xâu nhị phân độ dài đúng $n$. Hệ thống trả lời bằng một dòng chứa khoảng cách Hamming giữa $t$ và xâu bí mật $s$.
• Khi đã có đáp án, in ra một dòng ! pos0 pos1, trong đó $po{s}_0$ là một vị trí chứa ký tự 0 và $po{s}_1$ là một vị trí chứa ký tự 1, rồi kết thúc chương trình. Dòng này không tính là một câu hỏi.

Nếu bạn hỏi quá $15$ câu hỏi, in ra xâu truy vấn có độ dài khác $n$, hoặc đưa ra cặp vị trí sai, bạn sẽ nhận kết quả sai.

Quan trọng: Sau mỗi lần in ra, bạn phải flush output:

• C++: cout << endl; hoặc cout.flush();
• Python: print(..., flush=True)

Ràng buộc

• $2\le n\le 1000$
• Xâu bí mật chứa ít nhất một ký tự 0 và ít nhất một ký tự 1

Ví dụ

Với $n=2$ thì xâu bí mật chỉ có thể là 01 hoặc 10, và một câu hỏi duy nhất đã đủ để phân biệt hai trường hợp.