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

Мы загадали массив $$$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$$$.