G1. Интер-активный (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вы можете сделать не более $$$15\cdot n$$$ запросов. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Али настолько понравился подарок Бахамина (из задачи E), что он нелегально поехал из Казвина в Ливерпуль, чтобы подписать подарок у футболистов. Теперь Интерпол ищет его, но они предложили сделку: решите задачу, и он сможет остаться в Ливерпуле. Но так как он сейчас на стадионе, он не может её решить. Поэтому он попросил вас помочь ему.

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

Существует скрытая перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n\ge 4$$$, где $$$p_i \neq i$$$ для каждого $$$1 \leq i \leq n$$$.

Сначала вы должны сообщить жюри целое положительное число $$$k\le n$$$, которое будет неизменным в будущих запросах. Затем вам нужно найти перестановку $$$p$$$, используя некоторые запросы.

В каждом запросе вы даёте жюри перестановку $$$q_1, q_2, \ldots, q_n$$$. В ответ вы получите количество пар $$$(i, j)$$$, таких что выполняются все следующие условия:

  • $$$i \lt j$$$;
  • $$$p_{q_i} = q_j$$$;
  • $$$i \neq k$$$. ($$$k$$$ — это константа, которую вы дали жюри)

Вам дано $$$n$$$, и вам нужно найти перестановку $$$p$$$ не более чем за $$$15\cdot n$$$ запросов.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4 \leq n \leq 100$$$) — длина $$$p$$$.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

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

Затем вы должны вывести целое число $$$k$$$ ($$$1 \leq k \leq n$$$). Это не считается запросом.

Затем вы можете задать до $$$15\cdot n$$$ запросов.

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

  • $$$\texttt{?}\,q_1\,q_2\,\ldots\,q_n$$$

Жюри вернёт ответ на запрос.

Когда вы найдёте перестановку $$$p$$$, выведите одну строку в следующем формате:

  • $$$\texttt{!}\,p_1\,p_2\,\ldots\,p_n$$$

Это также не считается запросом.

После этого переходите к обработке следующего набора входных данных или завершите программу, если это последний набор входных данных.

Интерактор не адаптивен, что означает, что перестановка определяется до того, как участник выведет $$$k$$$.

Если ваша программа сделает более $$$15\cdot n$$$ запросов, ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит читать из закрытого потока.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взломы

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

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

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
4


1

5


1

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

1
? 1 2 3 4

! 3 1 4 2

3
? 1 2 5 4 3

? 2 1 4 3 5

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

В первом наборе входных данных $$$p = [3, 1, 4, 2]$$$. Решение выбрало $$$k=1$$$, затем запросило перестановку $$$q = [1, 2, 3, 4]$$$. Только пара $$$(3,4)$$$ удовлетворяет условиям.

Во втором наборе входных данных $$$p = [3, 1, 2, 5, 4]$$$. Решение выбрало $$$k=3$$$.

  • Для перестановки $$$q = [1, 2, 5, 4, 3]$$$ только пара $$$(1, 5)$$$ удовлетворяет условиям.
  • Для перестановки $$$q = [2, 1, 4, 3, 5]$$$ пары $$$(1, 2)$$$ и $$$(2, 4)$$$ удовлетворяют условиям.