Это интерактивная задача.
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,2)\). Для перемещения в клетку \((2,3)\) требуется \(1\) шаг, а для перемещения в клетку \((2,4)\) — \(2\) шага.
Обратите внимание, что ваши запросы могут быть другими. Это просто пример запросов, которые вы можете сделать.