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

Судьи работают над стратегией для программы жюри для модифицированной версии задачи J из текущего соревнования.

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

Судьи планируют создать AliceBot, который будет делать следующее. Существует две фазы: фаза вопросов и фаза ответов.

На фазе вопросов судья сообщает AliceBot целое число $N$. Затем AliceBot должен отвечать на вопросы, которые судья задает о перестановке.

На последующей фазе ответов AliceBot должен составить две различные перестановки $a_1, \dots, a_N$ и $b_1, \dots, b_N$, которые согласуются с ответами, полученными на предыдущей фазе.

Судья, задающий вопросы, имеет начальное терпение $P = 2N$. Каждый раз, когда судья задает вопрос, его терпение уменьшается.

Судья может задать три типа вопросов:

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

Вы можете считать, что терпение судьи никогда не опустится ниже 2 после того, как он задаст вопрос. Когда судья решает, что задал достаточно вопросов, AliceBot отправляется команда «!», переключающая его на фазу ответов.

На фазе ответов AliceBot сообщает судье две перестановки $a_1, \dots, a_N$ и $b_1, \dots, b_N$. Эти две перестановки должны быть согласованы со всеми ответами, данными на фазе вопросов, а количество позиций $i$, таких что $a_i \neq b_i$, должно быть не менее $\lceil p/2 \rceil$, где $p$ — терпение судьи в конце фазы вопросов.

Поскольку судья слишком ленив, вас просят реализовать AliceBot. Можно показать, что задача разрешима для любого возможного $N$ в рамках ограничений.

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

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

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

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

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

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

Пусть всего было задано $q_1$ вопросов типа 1, $q_2$ вопросов типа 2 и $q_3$ вопросов типа 3. Вы можете считать, что значение $p = 2N - 2q_1 - 2q_2 - q_3$ не меньше 2.

Для переключения на фазу ответов программа жюри выдает строку, состоящую из символа «!». После этого вы должны вывести две строки: первая строка содержит $N$ целых чисел $a_1, \dots, a_N$, разделенных пробелами, а вторая строка содержит $N$ целых чисел $b_1, \dots, b_N$, разделенных пробелами. Каждая из этих двух последовательностей должна быть перестановкой чисел $1, \dots, N$, и они должны различаться как минимум в $\lceil p/2 \rceil$ позициях.

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

Примеры

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

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

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

4
4
1
3 5 4 1 2
5 4 3 2 1