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

Алиса тайно загадывает перестановку первых $N$ целых чисел $a_1, a_2, \dots, a_N$ и сообщает $N$ Бобу. Боб задает вопросы, чтобы определить эту перестановку.

Он может задавать вопросы двух типов:

• Тип 1, формат «? 1 i j k»: Боб выбирает три различных целых числа $i, j, k$ ($1 \le i, j, k \le N$). Алиса смотрит на три числа $a_i, a_j$ и $a_k$ и сообщает Бобу значение их медианы (число, которое не является ни минимальным, ни максимальным).
• Тип 2, формат «? 2 i j»: Боб выбирает два различных целых числа $i, j$ ($1 \le i, j \le N$). Алиса отвечает $i$, если $a_i < a_j$, или $j$ в противном случае.

Игра кажется слишком простой для Боба, поэтому Алиса придумала новые правила. Во-первых, Боб может задать не более $2N$ вопросов типа 1 и только 2 вопроса типа 2. Во-вторых, Алиса может свободно менять перестановку, пока она остается согласованной со всеми ответами, данными ранее.

Помогите Бобу выиграть и напишите программу, которая определяет перестановку.

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

Сначала программа жюри сообщает вам одно целое число $N$ на отдельной строке ($4 \le N \le 60\,000$).

Затем вы можете задавать вопросы.

Вопрос типа 1 имеет формат «? 1 i j k» ($1 \le i, j, k \le N$; $i, j$ и $k$ попарно различны). Программа жюри выводит строку с одним целым числом: медианой значений $a_i, a_j$ и $a_k$. Вы можете задать вопрос этого типа не более $2N$ раз.

Вопрос типа 2 имеет формат «? 2 i j» ($1 \le i, j \le N$; $i \neq j$). Программа жюри выводит строку с одним целым числом: $i$, если $a_i < a_j$, или $j$, если $a_i > a_j$. Вы можете задать вопрос этого типа не более двух раз.

Когда перестановка однозначно определена, выведите ответ в формате «! a_1 a_2 \dots a_N».

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

Не забудьте вывести символ переноса строки и очистить буфер вывода после вывода вопроса или ответа, иначе вы можете получить ошибку «Idleness Limit Exceeded».

Примеры

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

5
4
4
2

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

? 1 1 2 3
? 2 2 4
? 1 1 5 4
! 3 5 4 1 2