C. Li Hua и шахматы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Li Ming и Li Hua играют в игру. У Li Hua есть шахматная доска размером $$$n\times m$$$. Обозначим $$$(r, c)$$$ ($$$1\le r\le n, 1\le c\le m$$$) как клетку в $$$r$$$-й строке сверху и в $$$c$$$-м столбце слева. Li Ming поставил короля на шахматную доску, и Li Hua нужно угадать его позицию.

Li Hua может задавать Li Ming не более $$$3$$$ вопросов. В каждом вопросе он может выбрать клетку и спросить минимальное количество шагов, необходимых для перемещения короля на выбранную клетку. Каждый вопрос является независимым, что означает, что король на самом деле не перемещается.

Король может переместиться из $$$(x,y)$$$ в $$$(x',y')$$$ тогда и только тогда, когда $$$\max\{|x-x'|,|y-y'|\}=1$$$ (как показано на следующем рисунке).

Позиция короля выбирается перед взаимодействием.

Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.

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

Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^3$$$).

Первая строка каждого набора входных данных содержит два целых числа $$$n,m$$$ ($$$1\le n,m\le 10^9$$$) — размер шахматной доски, после чего начинается взаимодействие.

Чтобы задать вопрос, выведите «? $$$r$$$ $$$c$$$» (без кавычек, $$$1 \leq r \leq n, 1 \leq c \leq m$$$). Затем вы должны ввести ответ со стандартного ввода — минимальное количество шагов, необходимое королю для перемещения в выбранную клетку.

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

Чтобы дать окончательный ответ, выведите «! $$$r$$$ $$$c$$$» (без кавычек, $$$(r,c)$$$ - это начальная координата короля). Обратите внимание, что вывод ответа не учитывается в ограничение в $$$3$$$ вопроса.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы

Для взлома используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$).

Первая и единственная строка каждого набора входных данных должна содержать четыре целых числа $$$n,m,r,c$$$ ($$$1\le r\le n\le 10^9,1\le c\le m\le 10^9$$$).

Пример
Входные данные
2
3 4

1

2

5 3

3

1

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


? 2 3

? 2 4

! 2 2

? 2 2

? 5 2

? 5 3

! 5 1
Примечание

В первом наборе входных данных король находится в точке $$$(2,2)$$$. Для перемещения в клетку $$$(2,3)$$$ требуется $$$1$$$ шаг, а для перемещения в клетку $$$(2,4)$$$ — $$$2$$$ шага.

Обратите внимание, что ваши запросы могут быть другими. Это просто пример запросов, которые вы можете сделать.