E. Classical Interactive Training
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a secret sequence $$$p_1, p_2, \cdots, p_{n}$$$, which is a permutation of $$$\{1,2,\cdots,n\}$$$.

We will define $$$ \text{idx}(x) $$$ as the index where the value $$$x$$$ is located.

You can ask two types of queries in the following format:

  • "1 x y"

This means that you select two integers $$$x$$$, $$$y$$$ ($$$1 \le x,y \le n$$$), and ask if the condition $$$\text{idx}(x) \lt \text{idx}(y)$$$ holds.

  • "2 x y z"

This means that you select three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \leq x, y, z \leq n$$$), and ask if $$$\text{idx}(y)$$$ is between $$$\text{idx}(x)$$$ and $$$\text{idx}(z)$$$. In other words, check if $$$\min(\text{idx}(x), \text{idx}(z)) \leq \text{idx}(y) \leq \max(\text{idx}(x), \text{idx}(z))$$$ holds.

Determine the permutation $$$p$$$ using no more than $$$1$$$ query of type $$$1$$$ and no more than $$$16n$$$ queries of type $$$2$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). The description of the test cases follows.

Interaction

The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 100$$$). At this moment, the permutation $$$p_1, p_2, \cdots, p_{n}$$$ is chosen.

To ask a type $$$1$$$ query, you need to pick two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$) and print the line of the following form:

  • "1 x y"

After that, you receive:

  • "1" if $$$\text{idx}(x) \lt \text{idx}(y)$$$ holds;
  • "0" otherwise.

To ask a type $$$2$$$ query, you need to pick three integers $$$x, y$$$ and $$$z$$$ ($$$1 \leq x, y, z \leq n$$$) and print the line of the following form:

  • "2 x y z"

After that, you receive:

  • "1" if $$$\min(\text{idx}(x), \text{idx}(z)) \leq \text{idx}(y) \leq \max(\text{idx}(x), \text{idx}(z))$$$ holds;
  • "0" otherwise.

Next, if your program has determined the permutation, print the line of the following form:

  • "! $$$p_1\ p_2\ \cdots \ p_n$$$"

Note that this line is not considered a query.

After this, proceed to the next test case.

If the number of queries you use exceeds the limit, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query or the answer for a test case, do not forget to output the end of line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.

The interactor in this task is not adaptive. In other words, the sequence $$$p$$$ is fixed in every test case and does not change during the interaction.

Hacks

To hack, follow the test format below.

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 20$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 100$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_{n}$$$, which represent a permutation of integers from $$$1$$$ to $$$n$$$.

Example
Input
2
3

1

1

0

4

0

1

1

1
Output


2 1 1 1

2 1 3 2

1 1 2

! 2 3 1

2 2 1 4

2 1 2 3

1 4 2

! 4 3 2 1
Note

In the first test case, the hidden permutation is $$$p=[2,3,1]$$$. We can get $$$\text{idx}(1)=3,\text{idx}(2)=1$$$, and $$$\text{idx}(3)=2$$$.

For the query "2 1 1 1", the jury returns "1" because $$$\min(\text{idx}(1), \text{idx}(1)) \leq \text{idx}(1) \leq \max(\text{idx}(1), \text{idx}(1))$$$ holds;

For the query "2 1 3 2", the jury returns "1" because $$$\min(\text{idx}(1), \text{idx}(2)) \leq \text{idx}(3) \leq \max(\text{idx}(1), \text{idx}(2))$$$ holds;

For the query "1 1 2", the jury returns "0" because $$$\text{idx}(1) \lt \text{idx}(2)$$$ does not hold.

In the second test case, the hidden permutation is $$$p=[4,3,2,1]$$$.

Please note that the example is only for understanding the statement, and the queries in the example do not guarantee to determine the unique permutation.