本届 EGOI 的闭幕式将有 $N$ 位重要宾客出席。他们都需要按照非常特定的顺序坐在前排，以符合外交礼仪的所有细节。确定正确的座位顺序让 Noemi 熬了两个通宵。

Veronica 正在监督闭幕式。她的众多职责之一是确保前排座位上有正确的名字标牌。只有一个小问题：Noemi 从未告诉她正确的座位顺序，而现在 Noemi 已经找不到了。幸运的是，摄影师 Dorka 有一个可能派上用场的应用程序（App）。

Dorka 必须准备好她的相机，以便为前排的宾客拍摄一些特定的照片。为了进行设置，她需要知道每张照片有多宽，因此 Noemi 为她制作了一个 App，可以快速输出她需要的信息。Veronica 现在想利用这个 App 来找到正确的座位安排。

这 $N$ 位重要宾客的编号为 $0$ 到 $N - 1$。前排的座位也从左到右编号为 $0$ 到 $N - 1$。对于每个 $I$（$0 \le I \le N - 1$），令 $g_I$ 表示应该坐在座位 $I$ 的宾客，并令 $s_I$ 表示宾客 $I$ 应该坐的座位。

图 1：有 5 位宾客的一排。对于这一排，$g = [3, 1, 0, 2, 4]$ 且 $s = [2, 1, 3, 0, 4]$。

该 App 的工作原理如下：

• Dorka 输入恰好三位不同宾客的编号 $I, J, K$。
• App 会告诉她，如果这三位选定的宾客都在照片中，照片中将显示的最少宾客人数。形式化地，App 将显示值 $\max(s_I, s_J, s_K) - \min(s_I, s_J, s_K) + 1$。

例如，参见图 1 中所示的情况：

• 宾客 $I = 0, J = 2, K = 4$ 分别在座位 $s_I = 2, s_J = 3, s_K = 4$。如果 Dorka 选择他们，App 将显示值 $\max(2, 3, 4) - \min(2, 3, 4) + 1 = 3$。 换句话说，包含宾客 0、2 和 4 的最窄照片恰好包含这三位宾客。
• 宾客 $I = 0, J = 4, K = 3$ 分别在座位 $s_I = 2, s_J = 4, s_K = 0$。如果 Dorka 选择他们，App 将显示值 $\max(2, 4, 0) - \min(2, 4, 0) + 1 = 5$。 换句话说，包含这三位给定宾客的照片必须包含所有 5 位宾客。

请使用 Dorka 的 App 帮助 Veronica 确定正确的座位顺序。更具体地说，你的程序应该确定并输出序列 $g_0, g_1, \dots, g_{N-1}$。总是恰好有两个正确答案（其中一个是另一个的翻转），你可以输出其中任意一个。你的得分将取决于你的解决方案对 App 进行的询问次数。

实现细节

这是一个交互式问题。你的程序将使用标准输入和输出与交互器（grader）按照以下格式进行通信。

你的程序应该首先读取一行输入，其中包含一个正整数 $T$，表示接下来的测试用例数量。

对于每个测试用例，你的程序应该首先读取一行输入，其中包含一个正整数 $N$，表示座位的数量，这也是宾客的数量。

要进行一次询问，你的程序应该输出一行格式为 ? I J K 的内容，其中 $0 \le I, J, K \le N - 1$ 是三个不同的整数。

在进行询问后，你的程序应该读取一行，其中包含一个正整数，即对你询问的回答。

要回答正确的座位顺序，你的程序应该输出一行格式为 ! g_0 ... g_{N-1} 的内容。

在解决所有 $T$ 个测试用例后，你的程序应该正常终止。

请注意，CMS 中用于测试你的解决方案的官方交互器可能是自适应的（adaptive）。也就是说，对于某些测试用例，宾客的排列并不是预先确定的。相反，交互器可能会根据你的程序已经提出的询问，来决定使用剩下哪些排列。

刷新缓冲区（Flushing）。如果你没有使用提供的模板，请确保在打印每行后刷新标准输出，否则你的程序可能会被判定为不正确（Not correct）。在 Python 中，如果你使用 input() 读取行，这会自动发生，你可以使用 print(..., flush=True) 来强制刷新。在 C++ 中，cout << endl; 除了打印换行符外还会刷新；如果使用 printf，请使用 fflush(stdout)。

数据范围

• $1 \le T \le 10$。
• $N$ 将为 $5$（仅限样例）、$8$、$40$ 或 $2000$。
• 对于每个测试用例，你最多可以进行 $10\,000$ 次询问。

子任务

你的程序将在分为多个子任务的若干测试用例上进行测试。要获得某个子任务的分数，你必须正确解决它包含的所有测试用例。

• 子任务 0 [0 分]：样例（$N = 5$）。
• 子任务 1 [9 分]：$N = 8$。
• 子任务 2 [11 分]：$N = 2000$，且宾客 0 和 1 相邻而坐。
• 子任务 3 [15 分]：$N = 40$。
• 子任务 4 [65 分]：$N = 2000$。

对于子任务 1 和 2，任何正确解决所有测试用例的解决方案都将获得全部满分。

对于子任务 3 和 4，你的解决方案必须正确解决所有测试用例才能获得任何分数，你的分数将取决于 $Q_s$，即你的解决方案在解决单个测试用例时所需的最大询问次数。令 $X_s = \max(1, Q_s/N)$。子任务 3 和 4 的分数计算如下：

$$\text{score}_3 = \min\left(15, 3 + \frac{19}{X_s^{1.5}}\right), \quad \text{score}_4 = \min\left(65, 3 + \frac{91}{X_s^{1.5}}\right)$$

每个子任务的 $\text{score}_s$ 值将四舍五入到最接近的整数，你的总分是这些分数的总和。为了获得满分，你需要在子任务 3 中使用最多 $55$ 次询问，在子任务 4 中使用最多 $2597$ 次询问。下面显示了 $Q_s$ 的示例值以及子任务 3 和 4 的对应得分。

样例

输入样例 1

1
5
3
3
5

输出样例 1

? 0 2 4
? 3 0 1
? 0 4 3
! 3 1 0 2 4

说明

样例输入包含一个测试用例（$T = 1$），其中有 $N = 5$ 位宾客。该测试用例中隐藏的宾客配置对应于图 1。

样例解决方案进行的第一次询问是 0 2 4。对该询问的回答 3 告诉我们，这些宾客以某种未知的顺序坐在相邻的三个连续座位上。

对第二次询问的回答 3 告诉我们关于宾客 3、0 和 1 的相同信息。

我们现在可以推断出宾客 0 必须坐在中间，宾客 2 和 4 在一侧，宾客 1 和 3 在另一侧。

在第三次询问之后，我们已经可以确定宾客必须以顺序 [3, 1, 0, 2, 4] 或相反的顺序 [4, 2, 0, 1, 3] 坐下。我们可以输出这两种顺序中的任意一种。

CMS 中的代码模板与评测细节

我们强烈建议使用为 C++ 和 Python 提供的代码模板。这些模板会检查与交互器的通信是否成功，并在不成功时优雅地终止。

如果你不使用提供的模板，在你的解决方案不正确的情况下，CMS 可能会显示错误的评测结果。例如，你可能会收到“Execution killed by signal”（由信号终止）或“Execution timed out (wall clock limit exceeded)”（超时），而不是“Output isn't correct”（输出不正确）。

我们还建议在提交之前使用测试工具（见下文）在本地测试你的解决方案。测试工具会检查你解决方案的输出，并报告无效询问的使用情况。

测试工具

为了方便测试你的解决方案，我们提供了一个可以从 CMS 下载的简单工具。该工具是可选使用的。请注意，CMS 上的官方交互器与该测试工具不同。

要使用该工具，你需要一个输入文件。你可以使用提供的示例输入 seatingplan.input0.txt 或制作你自己的输入。输入文件应首先包含一行，其中有测试用例的数量 $T$，然后每个测试用例有两行：一行包含数量 $N$，然后一行包含数字 $g_0, g_1, \dots, g_{N-1}$。

对于 Python 程序，假设为 seatingplan.py（通常运行为 pypy3 seatingplan.py），按如下方式运行测试工具：

python3 testing_tool.py pypy3 seatingplan.py < seatingplan.input0.txt

对于 C++ 程序，首先编译你的解决方案：

g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o seatingplan seatingplan.cpp

然后运行测试工具：

python3 testing_tool.py ./seatingplan < seatingplan.input0.txt