F. Запросы медианы
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Есть загаданная перестановка $$$p$$$ (нумерация начинается с $$$1$$$) из чисел от $$$1$$$ до $$$n$$$. Формально, для $$$1 \leq i \leq n$$$, $$$1 \leq p[i] \leq n$$$ и для $$$1 \leq i < j \leq n$$$, $$$p[i] \neq p[j]$$$. Известно, что $$$p[1]<p[2]$$$.

За $$$1$$$ запрос, вы даете $$$3$$$ различные целые числа $$$a,b,c$$$ ($$$1 \leq a,b,c \leq n$$$) и получаете медиану из $$$\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$$$.

В этом случае медиана — это $$$2$$$-й элемент (в $$$1$$$-индексации) последовательности, отсортированной в неубывающем порядке. Медиана чисел $$$\{4,6,2\}$$$ равна $$$4$$$, а медиана чисел $$$\{0,123,33\}$$$ равна $$$33$$$.

Можете ли вы найти загаданную перестановку за не более чем $$$2n+420$$$ запросов?

Примечание: интерактор не является адаптивным: перестановка зафиксирована до того, как сделаны какие-либо запросы.

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

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

Первая строка каждого набора входных данных состоит из одного целого числа $$$n$$$ $$$(20 \leq n \leq 100000)$$$ — длины загаданной перестановки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$100000$$$.

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

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

Чтобы выполнить запрос, выведите «? a b c», где $$$a,b,c$$$ — $$$3$$$ индекса, которые вы хотите использовать для запроса.

Числа должны удовлетворять требованиям $$$1 \leq a,b,c \leq n$$$ и $$$a \neq b$$$,$$$b \neq c$$$,$$$a \neq c$$$.

Для каждого запроса вы получите одно целое число $$$x$$$: медиану из $$$\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$$$.

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

Когда вы определите загаданную перестановку, выведите «! p[1] p[2] ... p[n]». Если перестановка определена верно, интерактор выведет «1». В противном случае интерактор выведет «-1» и завершит взаимодействие. Вы получите вердикт Неправильный ответ. Убедитесь, что вы сразу же вышли, чтобы избежать получения других вердиктов.

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

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

Взломы:

Для взлома используйте следующий формат теста:

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

Первая строка каждого набора входных данных должна содержать одно целое число $$$n$$$ ($$$20 \leq n \leq 100000$$$) — длину секретной перестановки.

Следующая строка должна содержать $$$n$$$ целых чисел $$$p[1],p[2],p[3],\ldots,p[n]$$$ такие, что $$$p[1]<p[2]$$$ и $$$p$$$ — перестановка чисел от $$$1$$$ до $$$n$$$.

Вы должны убедиться, что сумма $$$n$$$ по всем тестовым примерам не превышает $$$100000$$$.

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

6

9

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


? 1 5 2

? 20 19 2

! 9 10 19 7 16 18 11 14 15 6 20 8 17 4 5 3 12 2 13 1
Примечание

Загаданная перестановка — $$$\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$$$.

Для первого запроса значениями $$$(a,b,c)$$$ являются $$$(1,5,2)$$$. Поскольку $$$p[1]=9$$$, $$$p[5]=16$$$ и $$$p[2]=10$$$, то возвращаемое значение — медиана $$$\{|9-16|,|16-10|,|9-10|\}$$$, которая равна $$$6$$$.

Для второго запроса значения $$$(a,b,c)$$$ равны $$$(20,19,2)$$$. Поскольку $$$p[20]=1$$$, $$$p[19]=13$$$ и $$$p[2]=10$$$. Возвращаемое значение — медиана $$$\{|1-13|,|13-10|,|1-10|\}$$$, которая равна $$$9$$$.

Каким-то чудом мы выяснили, что загаданная перестановка — $$$\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$$$. Мы выводим ее и получаем от интерактора $$$1$$$, что означает, что мы правильно угадали перестановку.