Это интерактивная задача — ваша программа будет обмениваться данными с программой жюри через стандартный ввод и вывод (консоль).
Айбек агай спрятал Слона на шахматной доске $$$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$$$.
