這是一個互動式問題。

評審正在為本場比賽中問題 J 的修改版本開發評審程式的策略。

在該問題中，Alice 秘密發明了一個包含前 $N$ 個整數的排列 $a_1, a_2, \dots, a_N$，並將 $N$ 告訴 Bob。Bob 提出一些問題來識別這個排列。Alice 在過程中可以更改排列，只要它與她之前的回答一致即可。

評審計畫建立一個 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$，並告訴 Bob 它們的中位數（既不是最小值也不是最大值的那個數）。每個此類問題會使評審的耐心值減少 2。
• 類型 2，格式為 “? 2 i j”：評審選擇兩個不同的整數 $i, j$ ($1 \le i, j \le N$)，若 $a_i < a_j$ 則 AliceBot 回答 $i$，否則回答 $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$。這兩個排列必須與提問階段給出的所有回答一致，且滿足 $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$)。你接著輸出一行，包含一個整數：若 $a_i < a_j$ 則輸出 $i$，否則輸出 $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

說明

在範例中，評審詢問了三個問題，耐心值 $p$ 變為 $2(5) - 2(1) - 2(1) - 1(1) = 5$。因此，兩個排列必須在至少 $\lceil 5/2 \rceil = 3$ 個位置上不同。輸出的兩個排列在所有 5 個位置上皆不同，符合要求。