Đây là bài toán tương tác. Giới hạn là $18\,000$ truy vấn.

Ban giám khảo có một xâu bí mật gồm đúng 1000 chữ số nhị phân. Trong mỗi kiểm thử của bài toán, xâu được cố định trước và không thay đổi. Bạn phải tìm xâu này bằng các truy vấn.

Trong mỗi truy vấn, bạn chọn một đoạn $[a, b]$ ($1 \le a \le b \le 1000$) để hỏi. Sau đó ban giám khảo tung một đồng xu và trả về một trong hai giá trị sau, mỗi giá trị với xác suất 50%:

1. Số lượng chữ số 1 trong đoạn $[a, b]$;
2. Một giá trị từ $0$ đến $b - a + 1$ không bằng số lượng chữ số 1 trong đoạn đó, được chọn ngẫu nhiên đều.

Bạn không được phép dùng cùng một truy vấn hai lần. Tất cả các giá trị ngẫu nhiên trong bài toán đều có phân phối đều và độc lập.

Giao tiếp

Chương trình của thí sinh phải tương tác với chương trình của ban giám khảo bằng cách in các lệnh theo một trong những định dạng sau:

• ? a b. Truy vấn đoạn $[a, b]$. Để trả lời, chương trình của ban giám khảo in một số nguyên duy nhất: với xác suất 50%, đó là số lượng chữ số 1 trong đoạn $[a, b]$; nếu không, đó là một giá trị ngẫu nhiên từ $0$ đến $b - a + 1$ khác số lượng ấy.
• ! ans. Đáp án của bài toán, trong đó ans là một xâu độ dài 1000 gồm các chữ số 0 và 1. Sau lệnh này, chương trình của thí sinh phải kết thúc ngay lập tức.

Ví dụ

Dữ liệu vào 1

2
3
3
1
3

Dữ liệu ra 1

? 1 3
? 1 5
? 3 5
? 2 3
? 2 5
! 01101

Ghi chú

Ví dụ trên chỉ nhằm minh họa định dạng. Trong ví dụ này, xâu có độ dài 5. Trong kiểm thử thật đầu tiên cũng như tất cả các kiểm thử khác, độ dài của xâu cần đoán luôn bằng đúng 1000.