Đây là 1 bài interactive

Trên một bàn cờ vua kích thước \(N \times N\), hệ thống đang ẩn giấu tọa độ \((X, Y)\) của một quân Mã. Bạn có thể gửi các câu hỏi truy vấn về số bước đi tối thiểu của quân Mã từ bất kỳ ô \((r, c)\) nào tới ô bí mật \((X, Y)\).

Vì đây là dạng bài Interactive, chương trình của bạn sẽ giao tiếp trực tiếp với máy chấm qua luồng chuẩn. Ở mỗi lượt, hãy in ra câu hỏi theo định dạng ? r c và đọc kết quả trả về. Khi đã xác định được tọa độ chính xác, hãy in ra ! X Y và kết thúc chương trình. Hãy tìm ra vị trí của quân Mã trong giới hạn số lần hỏi cho phép!

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) - kích thước bàn cờ.
• Các dữ liệu tiếp theo được đọc động từ luồng chuẩn sau mỗi lần tương tác.

Constraints

• \(1 \le N \le 1000\).
• Số lần hỏi tối đa: \(60\) lần.

Output

• Mỗi câu hỏi in ra một dòng dạng ? r c (\(1 \le r, c \le N\)) và phải nhớ flush bộ đệm (ví dụ dùng endl trong C++).
• Kết quả cuối cùng in ra định dạng ! X Y.

Example

5
2
1
0

? 1 1
? 3 2
? 4 3
! 4 3

Scoring

• Subtask 1 (30 points): \(1 \le N \le 100\), giới hạn \(100\) lần hỏi.
• Subtask 2 (70 points): \(1 \le N \le 1000\), giới hạn \(60\) lần hỏi.