这是一个交互式问题。

评测系统正在为当前比赛中问题 J 的修改版本制定评测程序策略。

在该问题中，Alice 秘密发明了一个包含前 $N$ 个整数的排列 $a_1, a_2, \dots, a_N$，并告诉 Bob $N$ 的值。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$ 中的最小值。

设类型 1 的问题总数为 $q_1$，类型 2 的问题总数为 $q_2$，类型 3 的问题总数为 $q_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