这是一个交互式问题。

Alice 秘密构造了一个包含前 $N$ 个整数的排列 $a_1, a_2, \dots, a_N$，并告诉 Bob $N$ 的值。 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 次。

当排列被唯一确定时，请按 “! $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