CF1521C.Nastia and a Hidden Permutation

This is an interactive problem!

Nastia has a hidden permutation $p$ of length $n$ consisting of integers from $1$ to $n$. You, for some reason, want to figure out the permutation. To do that, you can give her an integer $t$ ($1 \le t \le 2$), two different indices $i$ and $j$ ($1 \le i, j \le n$, $i \neq j$), and an integer $x$ ($1 \le x \le n - 1$).

Depending on $t$, she will answer:

• $t = 1$: $\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$;
• $t = 2$: $\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$.

You can ask Nastia at most $\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$ times. It is guaranteed that she will not change her permutation depending on your queries. Can you guess the permutation?

这是一个交互式问题！

娜斯佳有一个长度为 $n$ 的隐藏排列 $p$，其中包含从 $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)})}$。

你最多可向娜斯佳提问 $\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$ 次。保证她在整个过程中不会根据你的提问而更改其排列。你能猜出这个排列吗？

The input consists of several test cases. In the beginning, you receive the integer $T$ ($1 \le T \le 10\,000$) — the number of test cases.

At the beginning of each test case, you receive an integer $n$ ($3 \le n \le 10^4$) — the length of the permutation $p$.

It's guaranteed that the permutation is fixed beforehand and that the sum of $n$ in one test doesn't exceed $2 \cdot 10^4$.

输入包含多个测试用例。首先，你将接收到一个整数 $T$（$1 \le T \le 10\,000$），表示测试用例的数量。

对于每个测试用例，首先你将接收到一个整数 $n$（$3 \le n \le 10^4$），表示排列 $p$ 的长度。

保证该排列在测试开始前已固定，且单个测试中所有 $n$ 的总和不超过 $2 \cdot 10^4$。

Consider the first test case.

The hidden permutation is $[3, 1, 4, 2]$.

We print: "? $2$ $4$ $1$ $3$" and get back $\min{(\max{(3, p_4}), \max{(4, p_1)})} = 3$.

We print: "? $1$ $2$ $4$ $2$" and get back $\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2$.

Consider the second test case.

The hidden permutation is $[2, 5, 3, 4, 1]$.

We print: "? $2$ $3$ $4$ $2$" and get back $\min{(\max{(2, p_3}), \max{(3, p_4)})} = 3$.

考虑第一个测试用例。

隐藏的排列为 $[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$。