Задача AF. Fencing the bishop ≡

Условие

Данная задача является интерактивной. Ваша программа будет взаимодействовать с программой жюри путем отправки и приема сообщений определенного вида.

Шахматная доска представляет из себя поле из 8 на 8 чередующихся белых и черных клеток. Столбцы шахматной доски обозначаются буквами от A до H, строки — цифрами от 1 до 8. Координаты клетки записываются как [столбец][строка], например, E2. Левый нижний угол, клетка A1, имеет черный цвет.

На шахматной доске расположился слон на клетке с цветом color. Напомним, что эта шахматная фигура может двигаться по диагонали в любом направлении на любое количество клеток. Целью является определить фактическую позицию слона, устанавливая наблюдение за некоторыми прямоугольными областями доски.

Ваша программа должна делать запросы вида "? A B", где A и B — координаты двух клеток игрового поля, левого нижнего и правого верхнего углов прямоугольника, за которым вы хотите установить мониторинг. После каждого запроса слон совершает ход, и вам сообщается в какие из наблюдаемых прямоугольников попал слон после этого хода.

Требуется определить текущее положение слона, сделав не более 6 запросов. Гарантируется, что перемещение слона определено заранее и не зависит от запросов.

Формат входных данных

В первой строке входных данных записана строка color, равная white или black — цвет клетки, на которой изначально стоит слон.

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

Чтобы сделать запрос, ваша программа должна вывести "? A B", где A, B — строки из двух символов, координаты левого нижнего и правого верхнего углов прямоугольника, за которым нужно установить наблюдение.

После установки наблюдения слон совершает ход, и программа жюри отвечает вашей программе строкой S из символов 1 или 0 — где i-й символ равен 1, если слон попал в i-й наблюдаемый прямоугольник.

Когда ваша программа определила текущее положение слона X, она должна вывести "! X", где X — строка из двух символов, координаты клетки слона. После вывода ответа программа должна завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error". Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

"A1"  ≤ A, B, X ≤  "H8"

A ≤ B

Пояснение к примерам

Перемещения слона и установленные области наблюдения из первого примера представлены на картинке.

Примеры тестов

white

0

01

000

0000

00000

100100

? B2 E4

? A4 C7

? A7 B8

? E4 F8

? H4 H8

? G1 H2

! E4

black

0

01

? A1 A1

? C3 C3

! C3