Số Nguyên Ẩn

Có một số nguyên ẩn $x$ thỏa mãn $1\le x\le {10}^9$. Nhiệm vụ của bạn là tìm ra $x$ bằng cách đặt câu hỏi.

Giao thức tương tác

Đây là bài toán tương tác (interactive). Chương trình của bạn giao tiếp với hệ thống đánh giá thông qua đầu vào/ra chuẩn.

Bạn có thể thực hiện hai loại thao tác:

• ? y (với $1\le y\le {10}^9$): Hỏi hệ thống liệu $y<x$ hay không. Hệ thống sẽ trả lời YES nếu $y<x$, hoặc NO nếu $y\ge x$.
• ! x: Khai báo đáp án và kết thúc chương trình.

Bạn được phép hỏi tối đa $30$ câu hỏi dạng ? trước khi khai báo đáp án.

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

• $1\le x\le {10}^9$
• Số truy vấn tối đa: $Q\le 30$

Ví dụ