Statement is not available in English language
G. Найти слона
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

«За какое минимальное количество ходов Слон достигнет столбца $$$X_1$$$ и строки $$$Y_1$$$?

После вопросов вам необходимо вывести позицию, на которой предположительно располагается Слон.

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

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

  • Любое ваше сообщение должно завершаться переводом строки.
  • После вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри:
    • 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$$$ $$$(A \le X_1 \le H$$$, $$$1 \le Y_1 \le 8)$$$ — вопросительный знак и координаты клетки из вопроса.

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

В ответ на вопрос программа жюри выводит целое число $$$K$$$ :

  • $$$K = -1$$$: Слон не может достигнуть клетки $$$X_1$$$$$$Y_1$$$.
  • Иначе $$$K$$$ равно количеству ходов от позиции Слона до клетки $$$X_1$$$$$$Y_1$$$.

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

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

Пример
Входные данные
2
-1
1
0
Выходные данные
? B6
? F3
? H6
? G5
! G5
Примечание

Определение: шахматная фигура «Слон» за один ход может переместиться на любую клетку по диагонали.

Формально, если Слон стоит на клетке $$$X$$$$$$Y$$$, то он может переместиться в клетку $$$U$$$$$$V$$$ только в случае, если $$$|U - X| = |V - Y|$$$.

Первый тестовый пример.

Айбек агай спрятал Слона на клетке G5.

  • От клетки G5 до B6 можно добраться только за два хода — или через клетку D8, или через E3, так как Слон ходит только по диагоналям.
  • До клетки F3 из G5 никак не добраться, так как Слон ходит только по клеткам одного и того же цвета.
  • До клетки H6 Слон добирается за один ход.
  • До своей позиции Слону не надо делать ходов, поэтому ответ на вопрос равен $$$0$$$.