Ghế Màu

Có $n$ chiếc ghế xếp thành vòng tròn, đánh số từ $1$ đến $n$. Ghế $i$ kề với ghế $i+1$ (với $1\le i<n$) và ghế $n$ kề với ghế $1$. Mỗi ghế được tô màu đỏ (R) hoặc xanh (B).

Nhiệm vụ của bạn là tìm hai ghế kề nhau có cùng màu.

Giao thức tương tác

Đây là bài toán tương tác. 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.

Đầu tiên, chương trình đọc số nguyên $n$.

Sau đó, bạn có thể thực hiện hai loại thao tác:

• ? i (với $1\le i\le n$): Hỏi màu của ghế thứ $i$. Hệ thống trả lời R (đỏ) hoặc B (xanh).
• ! i: Khai báo rằng ghế $i$ và ghế kế tiếp (ghế $i+1$, hoặc ghế $1$ nếu $i=n$) có cùng màu. Chương trình kết thúc sau thao tác này.

Bạn được phép hỏi tối đa $20$ câu hỏi dạng ?.

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

• $3\le n\le 2·{10}^5$
• $n$ là số lẻ
• Số truy vấn tối đa: $Q\le 20$

Ví dụ

Ghi chú

Vì $n$ là số lẻ, luôn tồn tại ít nhất một cặp ghế kề nhau có cùng màu (nguyên lý chuồng bồ câu: không thể tô xen kẽ hoàn hảo trên vòng tròn có số lẻ đỉnh).