D. Запросы НОД
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Загадана перестановка $$$p$$$ чисел $$$[0,1,2,\ldots,n-1]$$$. Ваша задача — найти $$$2$$$ индекса $$$x$$$ и $$$y$$$ ($$$1 \leq x, y \leq n$$$, возможно, $$$x=y$$$) такие, что $$$p_x=0$$$ или $$$p_y=0$$$. Чтобы это сделать, вы можете сделать не более чем $$$2n$$$ запросов.

В каждом запросе вы даете два целых числа $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) и получаете значение $$$\gcd(p_i,p_j)^\dagger$$$.

Обратите внимание, что перестановка $$$p$$$ зафиксирована до начала взаимодействия, и не зависит от ваших запросов.

$$$^\dagger$$$ $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$. Обратите внимание, что $$$\gcd(x,0)=\gcd(0,x)=x$$$ для всех положительных целых чисел $$$x$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^4$$$).

После считывания числа $$$n$$$ вы должны начать взаимодействие.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.

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

Взаимодействие начинается для каждого набора входных данных после считывания числа $$$n$$$.

Чтобы сделать запрос, выведите «? $$$i$$$ $$$j$$$» ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) без кавычек. После этого считайте одно целое число — ответ на ваш запрос $$$\gcd(p_i,p_j)$$$. Вы можете сделать не более чем $$$2n$$$ таких запросов в каждом наборе входных данных.

Если вы знаете ответ, выведите «! $$$x$$$ $$$y$$$» ($$$1 \leq x, y \leq n$$$) без кавычек. После этого считайте целое число $$$1$$$ или $$$-1$$$. Если $$$p_x=0$$$ или $$$p_y=0$$$, вы получите $$$1$$$, иначе вы получите $$$-1$$$. Если вы получили $$$-1$$$, ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

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

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

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

Взломы

Чтобы сделать взлом, используйте следующий формат.

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

Первая строка каждого набора входных данных должна содержать одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^4$$$).

Вторая строка должна содержать $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$. $$$p$$$ должно быть перестановкой чисел $$$[0,1,2,\ldots,n-1]$$$.

Сумма значений $$$n$$$ не должна превосходить $$$2 \cdot 10^4$$$.

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

1

1
5

2

4

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


? 1 2

! 1 2


? 1 2

? 2 3

! 3 3
Примечание

В первом примере взаимодействие происходит следующим образом.

РешениеЖюриКомментарий
$$$\texttt{2}$$$В тесте 2 набора входных данных.
$$$\texttt{2}$$$В первом наборе загадана перестановка $$$[1,0]$$$ длины $$$2$$$.
$$$\texttt{? 1 2}$$$$$$\texttt{1}$$$Решение запрашивает $$$\gcd(p_1,p_2)$$$, жюри отвечает $$$1$$$.
$$$\texttt{! 1 2}$$$$$$\texttt{1}$$$Решение знает, что либо $$$p_1=0$$$, либо $$$p_2=0$$$, и выводит ответ. Так как ответ правильный, жюри отвечает $$$1$$$ и переходит к следующему набору входных данных.
$$$\texttt{5}$$$Во втором наборе загадана перестановка $$$[2,4,0,1,3]$$$ длины $$$5$$$.
$$$\texttt{? 1 2}$$$$$$\texttt{2}$$$Решение запрашивает $$$\gcd(p_1,p_2)$$$, жюри отвечает $$$2$$$.
$$$\texttt{? 2 3}$$$$$$\texttt{4}$$$Решение запрашивает $$$\gcd(p_2,p_3)$$$, жюри отвечает $$$4$$$.
$$$\texttt{! 3 3}$$$$$$\texttt{1}$$$Решение каким-то образом определило, что $$$p_3=0$$$, и выводит ответ. Так как ответ верный, жюри отвечает $$$1$$$.

Обратите внимание, что пустые строки в примерах ввода и вывода показаны для ясности и отсутствуют в настоящем взаимодействии.

Помните про считывание $$$1$$$ или $$$-1$$$ после каждого набора входных данных.