关于托伦斜塔（Leaning Tower of Toruń）有许多传说。塔墙是一个圆，上面有 $N \ge 3$ 个均匀分布的门（换句话说，门是正 $N$ 边形的顶点）。门从 $0$ 到 $N-1$ 编号，但顺序是随机的。请参阅评分部分以获取有关此内容的更多详细信息。

其中一个鲜为人知的传说描述了塔的每一位新居民如何完成一项特定的挑战。挑战的目标是列出所有的门，从某一个门开始，然后绕着圆（顺时针或逆时针）走，恰好访问每个门一次。

这需要在不实际看到塔的情况下完成。相反，新居民可以提出以下形式的问题：“给定三个不同的门 $x, y, z$，哪几对门彼此距离最近：$\{x, y\}, \{y, z\}$ 还是 $\{z, x\}$？”。此类问题的答案是所有距离最近的门对（在 $\{x, y\}, \{y, z\}$ 和 $\{z, x\}$ 中）。距离即连接两扇门的最短线段的长度。你的任务是编写一个程序，通过询问少量此类问题来确定门的顺序。

交互

这是一个交互式任务。你应该编写一个程序，通过从标准输入读取并向标准输出写入来与交互器通信，从而找到任务的正确解。

在交互开始时，你的程序应从标准输入读取两个整数 $t$ 和 $k$ ($1 \le t \le 100, 1 \le k \le 12\,000$)，分别表示测试用例的数量和允许的平均查询次数上限。有关后者的更多信息，请参阅评分部分。

对于每个测试用例，你的程序应首先从标准输入读取一个整数 $n$ ($3 \le n \le 500$)，表示塔中门的数量。

然后，你的程序应按以下方式进行询问：

• 你的程序应向标准输出写入一行，格式为： ? x y z 其中 $x, y, z$ 是不同的整数 ($0 \le x, y, z \le n-1$)。这一行代表一个关于门 $x, y, z$ 的询问。

• 响应将给出为： $r$ $a_1 \ b_1$ $. \ .\ .$ $a_r \ b_r$ 其中 $r$ 是一个整数 ($1 \le r \le 3$)，表示距离最近的门对的数量。每一对由两个整数 $a_i$ 和 $b_i$ 描述 ($a_i, b_i \in \{x, y, z\}$ 且 $a_i < b_i$)。

当你确定了门的顺序后，你应该向标准输出写入一行，格式为： ! x0 x1 ... xn-1 其中 $x_0, x_1, \dots, x_{n-1}$ 是题目描述中所述的门的顺序。请注意，共有 $2n$ 种可能的正确答案，因为你可以从任何门开始并沿任一方向输出顺序。任何一种都会被接受。

请记住，在每次查询或回答后，你必须使用 C++ 中的 cout.flush()（或使用 printf 时的 fflush(stdout)）或 Python 中的 sys.stdout.flush() 来刷新输出缓冲区。否则，你的程序可能会收到“超出时间限制”（Time Limit Exceeded）的判决。

在向交互器写入答案后，你的程序应立即处理下一个测试用例，或者在所有测试用例处理完毕后结束交互。

你的程序不能打开任何文件或使用任何其他资源。它可以使用标准错误流进行调试，但请注意，写入此流会消耗时间。

另请注意，交互器是非自适应的，这意味着每个测试用例中的初始门顺序是预先固定的，并且在交互过程中不会改变。

样例

输入格式 1

1 100
6
? 0 1 2
2
0 2
1 2
? 4 1 3
1
1 4
? 0 5 1
3
0 5
0 1
1 5

输出格式 1

! 4 5 3 0 2 1

说明

样例说明：上图展示了沿塔墙排列的门及其编号。从左侧第一张图中，展示了由编号为 0, 1, 2 的门组成的三角形，对应于你程序的第一次查询。我们可以看到 $\{0, 2\}$ 和 $\{1, 2\}$ 这两对门距离最近。中间的图片展示了由编号为 1, 4, 3 的门组成的三角形，对应于你程序的第二次查询。我们可以清楚地看到 $\{1, 4\}$ 这一对门距离最近。从左侧第三张图中，展示了由编号为 0, 1, 5 的门组成的三角形，对应于你程序的第三次查询。我们可以清楚地看到所有门对彼此的距离相等。

请注意，序列 0, 2, 1, 4, 5, 3 或 5, 4, 1, 2, 0, 3（以及其他几种）在这种情况下也是正确的答案。

子任务

本题的评分分为若干子任务。每个子任务包含一个测试，该测试包含 $t = 100$ 个测试用例。对于每个测试，你的程序所询问的平均查询次数是通过将所有测试用例的查询总数除以测试用例数量来计算的。如果该平均值对于给定的子任务大于 $k$，你将获得该子任务 0 分。否则，对于子任务 1 到 4，你将获得该子任务的满分。

对于最后一个子任务，你的得分计算如下。设 $k^*$ 为你程序询问的实际平均查询次数。那么，得分由以下公式给出：

$$56 \cdot \min \left( 1, \frac{12000 - k^*}{7800} \right)$$

这意味着当 $k^*$ 从 12000 变为 4200 时，你的得分从 0 线性增加到 56。

请注意，如果你的程序对任何测试用例给出了错误的答案，无论查询次数多少，你都将获得该子任务 0 分。

各子任务的附加限制如下表所示：

此外，你可以假设每个测试用例都是通过首先从满足给定子任务限制的所有 $n$ 值中均匀随机选择 $n$，然后从满足给定子任务限制的所有 $n$ 个门的顺序中均匀随机选择门的顺序而生成的。