Где-то в сетке $5 \times 5$ спрятан сундук с сокровищами размером $2 \times 2$. Строки пронумерованы от 1 до 5, так же как и столбцы, при этом ячейка $(1, 1)$ является левым верхним углом сетки. Ваша цель — найти сокровище, сделав не более 5 запросов. Вы можете отправить запрос к любой ячейке сетки, чтобы узнать, находится ли в ней какая-либо часть сундука. После выполнения не более 5 запросов вы должны вывести координаты левого верхнего угла сундука.

На рисунке ниже показан пример расположения сундука $2 \times 2$ в сетке $5 \times 5$.

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

Ваша программа может сделать до 5 запросов о местоположении сокровища. Чтобы сделать запрос, выведите новую строку вида:

? i j

где $i$ и $j$ — целые числа от 1 до 5. Вы спрашиваете, содержит ли ячейка в $i$-й строке и $j$-м столбце часть сундука. После каждого запроса интерактор ответит $0$, если ячейка не содержит никакой части сокровища, или $1$, если содержит.

Определив правильный ответ, выведите его на новой строке в виде:

! i j

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

Не забудьте сбросить буфер вывода после каждого отправленного запроса.

Если интерактор получит некорректные или неожиданные данные, он выведет $-1$ и немедленно завершит работу. Ваша программа должна корректно завершиться, чтобы получить вердикт «верно», в противном случае полученный вердикт может быть произвольным, указывающим на то, что ваше решение неверно.

Для тестирования предоставляется инструмент на языке Python. Используйте его следующим образом (возможно, вам придется заменить python3 на python):

python3 testing_tool.py However-you-run-your-program

Инструмент предоставляется «как есть», и вы можете свободно вносить в него любые изменения или дополнения. Инструмент пытается обнаруживать и сообщать о распространенных ошибках, но нет гарантии, что программа, прошедшая проверку этим инструментом, будет принята.

Примеры