這是一個互動式問題。

Alice 秘密地發明了一個由前 $N$ 個整數組成的排列 $a_1, a_2, \dots, a_N$，並將 $N$ 告訴 Bob。 Bob 透過提問來識別這個排列。 他可以詢問兩種類型的問題：

• 類型 1，格式為「? 1 i j k」：Bob 選擇三個不同的整數 $i, j, k$ ($1 \le i, j, k \le N$)，Alice 查看這三個整數 $a_i, a_j, a_k$，並告訴 Bob 它們的中位數（即既不是最小值也不是最大值的那個數）。
• 類型 2，格式為「? 2 i j」：Bob 選擇兩個不同的整數 $i, j$ ($1 \le i, j \le N$)，若 $a_i < a_j$，Alice 回答 $i$，否則回答 $j$。

這個遊戲對 Bob 來說似乎太簡單了，所以 Alice 發明了新規則。首先，Bob 最多只能詢問 $2N$ 次類型 1 的問題，且最多只能詢問 2 次類型 2 的問題。其次，只要與之前給出的所有答案一致，Alice 可以隨意更改排列。

請幫助 Bob 獲勝，並編寫程式來識別該排列。

互動

首先，評測系統會在一行中告訴你一個整數 $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$)。評測系統隨後會輸出一行，包含一個整數：若 $a_i < a_j$ 則輸出 $i$，若 $a_i > a_j$ 則輸出 $j$。此類問題最多可詢問 2 次。

當排列被唯一確定時，請以「! a1 a2 ... aN」的格式輸出答案。

請注意，互動是適應性的：只要與過去的答案一致，評測系統可以隨時更改排列。特別地，如果你在答案尚未唯一確定時嘗試猜測，評測系統可能會立即選擇另一個排列並判定你錯誤。

在輸出問題或答案後，請務必輸出換行符號並刷新輸出緩衝區，否則你可能會收到「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