D. Омкар и смысл жизни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оказывается, смысл жизни — это перестановка $$$p_1, p_2, \ldots, p_n$$$ целых чисел $$$1, 2, \ldots, n$$$ ($$$2 \leq n \leq 100$$$). Омкар, создавший все живое, знает эту перестановку и позволит вам выяснить ее с помощью некоторых запросов.

Запрос состоит из массива $$$a_1, a_2, \ldots, a_n$$$ целых чисел от $$$1$$$ до $$$n$$$. $$$a$$$ — это не обязательно перестановка. Омкар сначала вычислит попарную сумму $$$a$$$ и $$$p$$$, то есть вычислит массив $$$s$$$, где $$$s_j = p_j + a_j$$$ для всех $$$j = 1, 2, \ldots, n$$$. Затем он найдет наименьший индекс $$$k$$$ такой, что $$$s_k$$$ встречается в $$$s$$$ более одного раза, и скажет вам $$$k$$$. Если такого индекса $$$k$$$ не существует, то он скажем вам $$$0$$$.

Можно выполнить не более $$$2n$$$ запросов. Выясните смысл жизни $$$p$$$.

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

Начните взаимодействие с чтения одного целого числа $$$n$$$ ($$$2 \leq n \leq 100$$$)  — длины перестановки $$$p$$$.

Затем вы можете делать запросы. Запрос состоит из одной строки «$$$? \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_n$$$» ($$$1 \leq a_j \leq n$$$).

Ответом на каждый запрос будет одно целое число $$$k$$$, как описано выше ($$$0 \leq k \leq n$$$).

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

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

Чтобы вывести ответ, выведите одну строку «$$$! \enspace p_1 \enspace p_2 \enspace \ldots \enspace p_n$$$» затем завершите работу.

Вы можете сделать не более $$$2n$$$ запросов. Вывод ответа не считается запросом.

Формат взлома

Для взлома сначала выведите строку, содержащую $$$n$$$ ($$$2 \leq n \leq 100$$$), затем выведите другую строку, содержащую скрытую перестановку $$$p_1, p_2, \ldots, p_n$$$ чисел от $$$1$$$ до $$$n$$$.

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

2

0

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

? 4 4 2 3 2

? 3 5 1 5 5

? 5 2 4 3 1

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

В примере скрытая перестановка $$$p$$$ равна $$$[3, 2, 1, 5, 4]$$$. Было сделано три запроса.

Первый запрос — $$$a = [4, 4, 2, 3, 2]$$$. Это дает $$$s = [3 + 4, 2 + 4, 1 + 2, 5 + 3, 4 + 2] = [7, 6, 3, 8, 6]$$$. $$$6$$$ — единственное число, которое встречается более одного раза, и впервые оно появляется на индексе $$$2$$$, что делает ответ на запрос $$$2$$$.

Второй запрос — $$$a = [3, 5, 1, 5, 5]$$$. Это дает $$$s = [3 + 3, 2 + 5, 1 + 1, 5 + 5, 4 + 5] = [6, 7, 2, 10, 9]$$$. Здесь нет чисел, которые встречаются более одного раза, поэтому ответ на запрос — $$$0$$$.

Третий запрос — $$$a = [5, 2, 4, 3, 1]$$$. Это дает $$$s = [3 + 5, 2 + 2, 1 + 4, 5 + 3, 4 + 1] = [8, 4, 5, 8, 5]$$$. $$$5$$$ и $$$8$$$ встречаются здесь более одного раза. $$$5$$$ впервые появляется на индексе $$$3$$$, а $$$8$$$ впервые появляется на индексе $$$1$$$, причем $$$1 < 3$$$, что делает ответ на запрос $$$1$$$.

Обратите внимание, что пример приведен только для того, чтобы показать, как работает взаимодействие; не гарантируется, что приведенные выше запросы представляют собой правильную стратегию, с помощью которой можно определить ответ.