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

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

Настя загадала перестановку $$$p$$$ длины $$$n$$$, состоящую из элементов от $$$1$$$ до $$$n$$$. Неизвестно по какой причине вы хотите восстановить перестановку. Для того, чтобы сделать это, вы даете Насте целое число $$$t$$$ ($$$1 \le t \le 2$$$), два различных индекса $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$) и целое число $$$x$$$ ($$$1 \le x \le n - 1$$$).

В зависимости от $$$t$$$ она ответит:

  • $$$t = 1$$$: $$$\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$$$;
  • $$$t = 2$$$: $$$\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$$$.

Вы можете спросить Настю не более $$$\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$$$ раз. Гарантируется, что она не будет менять перестановку в зависимости от ваших вопросов. Удастся ли вам восстановить перестановку?

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

Входные данные состоят из нескольких наборов. В начале вам выдается целое число $$$T$$$ ($$$1 \le T \le 10\,000$$$) — количество наборов входных данных.

В начале каждого набора вам выдается целое число $$$n$$$ ($$$3 \le n \le 10^4$$$) — длина перестановки $$$p$$$.

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

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

Чтобы задать вопрос, выведите «? $$$t$$$ $$$i$$$ $$$j$$$ $$$x$$$» ($$$t = 1$$$ или $$$t = 2$$$, $$$1 \le i, j \le n$$$, $$$i \neq j$$$, $$$1 \le x \le n - 1$$$). Затем вы должны считать ответ.

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

Чтобы дать ответ, выведите «! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_{n}$$$» (без кавычек). Заметьте, что вывод ответа не считается одним из $$$\lfloor \frac {3 \cdot n} {2} \rfloor + 30$$$ запросов.

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

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

Взломы

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

В первой строке должно находиться единственное целое число $$$T$$$ ($$$1 \le T \le 10\,000$$$) — количество наборов входных данных.

Для каждого набора входных данных в первой строке выведите целое число $$$n$$$ ($$$3 \le n \le 10^4$$$) — длина загаданной перестановки $$$p$$$.

Во второй строке выведите $$$n$$$ разделенных пробелами целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$), где $$$p$$$ является перестановкой.

При этом сумма $$$n$$$ по всем наборам должна не превосходить $$$2 \cdot 10^4$$$.

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

3

2

5

3
Выходные данные
? 2 4 1 3

? 1 2 4 2

! 3 1 4 2

? 2 3 4 2

! 2 5 3 4 1
Примечание

Рассмотрим первый набор входных данных. Загаданной перестановкой является $$$[3, 1, 4, 2]$$$.

Мы выводим «? $$$2$$$ $$$4$$$ $$$1$$$ $$$3$$$» и получаем в ответ $$$\min{(\max{(3, p_4}), \max{(4, p_1)})} = 3$$$.

Мы выводим «? $$$1$$$ $$$2$$$ $$$4$$$ $$$2$$$» и получаем в ответ $$$\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2$$$.

Рассмотрим второй набор входных данных. Загаданной перестановкой является $$$[2, 5, 3, 4, 1]$$$.

Мы выводим «? $$$2$$$ $$$3$$$ $$$4$$$ $$$2$$$» и получаем в ответ $$$\min{(\max{(2, p_3}), \max{(3, p_4)})} = 3$$$.