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

Мы загадали массив $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) и спрятали в нём один ноль! Более формально, среди чисел массива ровно одно значение равно нулю.

Ваша задача — найти, под каким индексом спрятан ноль, то есть найти такое $i$, что $a_i = 0$.

Для этого вы можете сделать некоторое количество запросов следующего вида. По трём различным индексам $i, j, k$ вы можете узнать значение выражения $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$. Другими словами, мы сообщим вам разность между максимальным и минимальным числом среди $a_i$, $a_j$ и $a_k$.

Вы можете сделать не более $2 \cdot n - 2$ таких запросов, после чего у вас будет две попытки угадать, под каким индексом спрятан ноль. Формально, вы должны сообщить нам два числа $i$ и $j$, и ваш ответ будет считаться правильным, если $a_i = 0$ или $a_j = 0$.

Сможете ли вы угадать, где мы спрятали ноль?

Обратите внимание, что в каждом тесте массив фиксирован и не изменяется во время игры. Иными словами, интерактор не адаптивен.

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

Чтобы задать запрос, выведите «? $i$ $j$ $k$» (без кавычек, $1 \le i, j, k \le n$, индексы должны быть различны). Затем вы должны считать ответ, который будет равен $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$.

Ответ $-1$ означает, что ваша программа сделала некорректный запрос. Ваша программа должна немедленно завершиться после прочтения ответа $-1$, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока. Обратите внимание, что если запрос корректный, ответ на него никогда не будет равен $-1$, так как $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) \geq 0$.

Чтобы дать ответ, выведите «! $i$ $j$» (без кавычек). Вывод одного и того же индекса дважды (то есть $i = j$) разрешен. Заметьте, что вывод ответа не считается одним из $2 \cdot n - 2$ запросов. После этого ваша программа должна продолжить обработку следующих наборов входных данных, либо завершиться, если наборов не осталось.

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

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

Взломы

Первая строка должна содержать целое число $t$ ($1 \le t \le 500$) — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать целое число $n$ ($4 \le n \le 1000$) — длину загаданного массива.

Вторая строка каждого набора должна содержать $n$ целых чисел, разделенных пробелами — $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$). Также в этом массиве должен быть ровно один ноль.

Сумма $n$ по всем наборам не должна превосходить $3000$.