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

У жюри была тождественная перестановка $$$a$$$ длины $$$n$$$ ($$$a_i = i$$$).

Жюри выбрало три целых числа $$$i$$$, $$$j$$$, $$$k$$$ такие, что $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$. После этого жюри развернуло отрезки $$$[i, j - 1]$$$ и $$$[j, k]$$$ в последовательности $$$a$$$.

Разворачивание подотрезка $$$[l, r]$$$ последовательности $$$a$$$ означает переворот подотрезка элементов $$$a_l, a_{l+1}, \ldots, a_r$$$ в последовательности, то есть $$$a_l$$$ меняется местами с $$$a_r$$$, $$$a_{l+1}$$$ с $$$a_{r-1}$$$, и т. д..

Вам дано число $$$n$$$. Вы должны найти $$$i$$$, $$$j$$$, $$$k$$$ с помощью некоторых запросов.

За один запрос вы можете выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) и узнать количество инверсий на подотрезке $$$[l, r]$$$ последовательности $$$a$$$. Жюри скажет вам количество пар $$$(i, j)$$$ таких, что $$$l \leq i < j \leq r$$$ и $$$a_i > a_j$$$.

Найдите числа $$$i$$$, $$$j$$$, $$$k$$$, выбранные жюри, сделав не более $$$40$$$ запросов.

Жюри фиксирует числа $$$i$$$, $$$j$$$ и $$$k$$$ до запуска вашей программы и не меняет их в зависимости от ваших запросов.

Чтобы спросить количество инверсий на отрезке $$$[l, r]$$$, выведите «? l r», где ($$$1 \leq l \leq r \leq n$$$). Вы можете сделать не более $$$40$$$ таких запросов в каждом тестовом случае. В ответ вы получите целое число $$$x$$$.

• Если $$$x = -1$$$, ваша программа сделала некорректный запрос или превысила допустимое количество запросов для данного набора. В таком случае ваша программа должна немедленно завершиться (иначе решение может получить произвольный вердикт вместо Неправильный ответ).
• Иначе $$$x$$$ равен количеству инверсий на подотрезке $$$[l, r]$$$ последовательности $$$a$$$.

Чтобы дать ответ, выведите «! i j k», где $$$i$$$, $$$j$$$, $$$k$$$ — числа, которые, как вы считаете, загадало жюри. После этого вы должны перейти к следующему набору или завершить программу.

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

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

Взломы

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

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

Каждая из следующих $$$t$$$ строк содержит четыре целых числа $$$n$$$, $$$i$$$, $$$j$$$, $$$k$$$ ($$$4 \leq n \leq 10^9$$$, $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$).