这是一个交互问题!
Nastia 有一个隐藏排列 $$$p$$$,长度为 $$$n$$$,由从 $$$1$$$ 到 $$$n$$$ 的整数组成。出于某种原因,你想弄清楚排列。为此,您可以给她一个整数 $$$t$$$ ($$$1 \le t \le 2$$$)、两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$) 和一个整数 $$$x$$$ ($$$1 \le x \le n - 1$$$)。
根据 $$$t$$$,她会回答:
- $$$t = 1$$$: $$$\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$$$;
- $$$t = 2$$$: $$$\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$$$。
您最多可以询问 Nastia $$$\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$$$ 次。保证她不会根据您的询问改变她的排列。你能猜出排列吗?
输入
输入由多个测试用例组成。一开始,您会收到整数 $$$T$$$ ($$$1 \le T \le 10\,000$$$) — 测试用例的数量。
在每个测试用例的开头,您会收到一个整数 $$$n$$$ ($$$3 \le n \le 10^4$$$) — 排列 $$$p$$$ 的长度。
保证排列预先固定,并且一次测试中 $$$n$$$ 的总和不超过 $$$2 \cdot 10^4$$$。
互动
要提问,请打印 "? $$$t$$$ $$$i$$$ $$$j$$$ $$$x$$$" ($$$t = 1$$$ 或 $$$t = 2$$$, $$$1 \le i, j \le n$$$, $$$i \neq j$$$, $$$1 \le x \le n - 1$$$)然后,你应该阅读答案。
如果我们用 $$$−1$$$ 回答而不是有效答案,则意味着您超出了查询数量或进行了无效查询。收到 $$$−1$$$ 后立即退出,您将看到错误答案的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
要打印答案,请打印 "! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_{n}$$$ (不带引号)。请注意,答案不算作 $$$\lfloor \frac {3 \cdot n} {2} \rfloor + 30$$$ 查询之一。
打印查询或打印答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解该解决方案,请使用以下测试格式。
第一行应包含一个整数 $$$T$$$ ($$$1 \le T \le 10\,000$$$) — 测试用例的数量。
对于第一行中的每个测试用例,打印一个整数 $$$n$$$ ($$$3 \le n \le 10^4$$$) — 隐藏排列 $$$p$$$ 的长度。
在第二行中打印 $$$n$$$ 以空格分隔的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p$$$ 是排列。
请注意,所有测试用例的 $$$n$$$ 总和不应超过 $$$2 \cdot 10^4$$$。
示例
输入 #1
2 4 3 2 5 3
输出 #1
? 2 4 1 3 ? 1 2 4 2 ! 3 1 4 2 ? 2 3 4 2 ! 2 5 3 4 1
注意
考虑第一个测试用例。
隐藏排列为 $$$[3, 1, 4, 2]$$$。
我们打印:“? $$$2$$$ $$$4$$$ $$$1$$$ $$$3$$$" 并返回 $$$\min{(\max{(3, p_4}), \max{(4, p_1)})} = 3$$$。
我们打印:“? $$$1$$$ $$$2$$$ $$$4$$$ $$$2$$$" 并返回 $$$\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2$$$。
考虑第二个测试用例。
隐藏排列为 $$$[2, 5, 3, 4, 1]$$$。
我们打印:“? $$$2$$$ $$$3$$$ $$$4$$$ $$$2$$$" 并返回 $$$\min{(\max{(2, p_3}), \max{(3, p_4)})} = 3$$$。