410410: GYM104018 C Найти ладью

C. Найти ладьюограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Это интерактивная задача — ваша программа будет обмениваться данными с программой жюри через стандартный ввод и вывод (консоль).

Айбек агай спрятал ладью на шахматной доске $$$8 \times 8$$$. Вы очень хотите узнать её координаты.

Столбцы на шахматной доске обозначаются латинской заглавной буквой от $$$A$$$ до $$$H$$$, а строки — целым числом от $$$1$$$ до $$$8$$$. Например, клетка $$$D7$$$ расположена в $$$4$$$-м столбце и $$$7$$$-й строке.

Чтобы найти координаты ладьи, вы можете задавать Айбек агаю не более 4 раз следующий вопрос:

«Рассмотрим прямоугольник, образованный столбцами от $$$X_1$$$ до $$$X_2$$$ и строками от $$$Y_1$$$ до $$$Y_2$$$. Сколько клеток в данном прямоугольнике бьётся спрятанной ладьёй?»

Если ладья стоит в клетке $$$(X_R, Y_R)$$$, то клетка $$$(X, Y)$$$ бьётся ладьёй при выполнении хотя бы одного из условий:

• $$$X = X_R$$$
• $$$Y = Y_R$$$

В частности, это означает, что ладья бьёт клетку $$$(X_R, Y_R)$$$, на которой она расположена.

Выходные данные

Обратите внимание, что

• Любое ваше сообщение должно завершаться переводом строки.
• После вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри:
  • C++: cout « endl (перевод строки + очистка буфера), cout.flush() или fflush(stdout);
  • Java: System.out.println() (перевод строки + очистка буфера), System.out.flush();
  • Python: print() (перевод строки + очистка буфера), stdout.flush().
  • Pascal: flush(output).
• При решении на С++ не отключайте синхронизацию cin/cout.

Протокол взаимодействия

Все координаты столбцов должны выводиться только заглавными буквами.

Вопрос задаётся в формате $$$\textbf{?}$$$ $$$X_1Y_1$$$ $$$X_2Y_2$$$ ($$$A \le X_1 \le X_2 \le H$$$, $$$1 \le Y_1 \le Y_2 \le 8$$$) — вопросительный знак, координаты левого нижнего и правого верхнего углов прямоугольника из вопроса.

Всего вы можете задать вопрос не более 4 раз.

В ответ на вопрос программа жюри выводит целое число $$$K$$$ ($$$-1 \le K \le 8 \times 8$$$):

• При получении ответа $$$K = -1$$$ ваша программа должна немедленно завершиться. Данная ситуация означает вердикт Presentation error (некорректный формат запроса) или Wrong answer (превышено количество запросов).
• Иначе $$$K$$$ равно количеству клеток в прямоугольнике со столбцами от $$$X_1$$$ до $$$X_2$$$ и строками от $$$Y_1$$$ до $$$Y_2$$$, находящихся под боем спрятанной ладьи.

Окончательный ответ выводится в формате $$$\textbf{!}$$$ $$$X_RY_R$$$ ($$$A \le X_R \le H$$$, $$$1 \le Y_R \le 8$$$) — восклицательный знак и предполагаемые координаты ладьи.

После вывода окончательного ответа ваша программа обязательно должна завершиться.

ПримерВходные данные

5
4
0
1

Выходные данные

? B5 F6
? F1 G4
? F7 F8
? G5 G5
! G5

Примечание

В тестовом примере ладья стоит на клетке $$$G5$$$.

1. Задаётся вопрос о прямоугольнике со столбцами от $$$B$$$ до $$$F$$$ и строками от $$$5$$$ до $$$6$$$.

   Так как ладья находится в строке $$$5$$$, то она бьёт клетки $$$B5$$$, $$$C5$$$, $$$D5$$$, $$$E5$$$, $$$F5$$$ — всего 5 клеток.

2. Задаётся вопрос о прямоугольнике со столбцами от $$$F$$$ до $$$G$$$ и строками от $$$1$$$ до $$$4$$$.

   Так как ладья находится в столбце $$$G$$$, то она бьёт клетки $$$G1$$$, $$$G2$$$, $$$G3$$$, $$$G4$$$ — всего 4 клетки.

3. Задаётся вопрос о прямоугольнике с единственным столбцом $$$F$$$ и строками от $$$7$$$ до $$$8$$$.

   Ладья не бьёт ни одной клетки в данном прямоугольнике — поэтому ответ 0.

4. Задаётся вопрос о прямоугольнике с единственным столбцом $$$G$$$ и единственной строкой $$$5$$$ — прямоугольник состоит из одной клетки.

   Ладья стоит именно на этой клетке, поэтому она её бьет — ответ 1.

5. Выводится ответ с координатами ладьи.