Statement is not available in English language
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. Выводится ответ с координатами ладьи.