This is an interactive problem.

This is the hard version of the problem. The only difference is that $$$n \le 890$$$ in this version. You can make hacks only if all versions of the problem are solved.

There is a hidden permutation $$$p$$$, which is a permutation of $$$\{1,2,\ldots,n\}$$$. Let $$$pos_i$$$ denote the position of the value $$$i$$$ in $$$p$$$, i.e., $$$pos_{p_i} = i$$$.

To find this permutation, you can ask four types of queries:

"$$$1\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ \ldots,\ i_m$$$ must be distinct). Let $$$k = \min(60, m)$$$. The jury will return the top $$$k$$$ largest number(s) in $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ in increasing order.
"$$$2\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ \ldots,\ i_m$$$ must be distinct). Let $$$k = \min(60, m)$$$. The jury will return the top $$$k$$$ largest number(s) in $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ in increasing order.
"$$$3\ m\ i_1\ i_2\ ...\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ ...,\ i_m$$$ must be distinct). Let $$$k = \min(300, m)$$$. The jury will return the top $$$k$$$ largest number(s) in $$$[p_{i_1}, p_{i_2}, ..., p_{i_m}]$$$ in increasing order.
"$$$4\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ \ldots,\ i_m$$$ must be distinct). Let $$$k = \min(300, m)$$$. The jury will return the top $$$k$$$ largest number(s) in $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ in increasing order.

Let $$$c_i$$$ be the usage count of queries of type $$$i$$$ $$$(1 \le i \le 4)$$$. Your query count must satisfy the following constraints:

$$$c_1+c_2+c_3+c_4 \le 30.$$$
$$$c_3+c_4 \le 1.$$$

Input

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

Interaction

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 890$$$). At this moment, the permutation $$$p$$$ is chosen. The interactor in this task is not adaptive. In other words, the permutation $$$p$$$ is fixed in every test case and does not change during the interaction.

To ask a query of type $$$1$$$, you need to print the line of the following form (without quotes):

"$$$1\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ must be distinct)

After that, you receive $$$k=\min(60,m)$$$ integer(s) — the top $$$k$$$ largest number(s) in $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ in increasing order.

To ask a query of type $$$2$$$, you need to print the line of the following form (without quotes):

"$$$2\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ must be distinct)

After that, you receive $$$k=\min(60,m)$$$ integer(s) — the top $$$k$$$ largest number(s) in $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ in increasing order.

To ask a query of type $$$3$$$, you need to print the line of the following form (without quotes):

"$$$3\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ must be distinct)

After that, you receive $$$k=\min(300,m)$$$ integer(s) — the top $$$k$$$ largest number(s) in $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ in increasing order.

To ask a query of type $$$4$$$, you need to print the line of the following form (without quotes):

"$$$4\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ must be distinct)

After that, you receive $$$k=\min(300,m)$$$ integer(s) — the top $$$k$$$ largest number(s) in $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ in increasing order.

Next, if your program has found the permutation $$$p$$$, print the line of the following form (without quotes):

"$$$!\ p_1\ p_2\ \ldots\ p_n$$$"

Note that this line is not considered a query and is not taken into account when counting the number of queries asked.

After this, proceed to the next test case.

After printing a query or the answer for a test case, do not forget to output the end of the 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.

Hacks

To hack, follow the test format below.

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

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 890$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$, which is a permutation of $$$\{1,2,\ldots,n\}$$$.

Note

In the first test case, the hidden permutation is $$$p = [3, 1, 2]$$$. Thus, $$$pos = [2, 3, 1]$$$.

For the query "3 2 3 1", the jury returns $$$2$$$ and $$$3$$$ because $$$2$$$ and $$$3$$$ are the top $$$k$$$ largest number(s) in $$$[p_3, p_1]$$$, where $$$k = \min(300, m) = \min(300, 2) = 2$$$.

For the query "2 1 2", the jury returns $$$3$$$ because $$$3$$$ is the top $$$k$$$ largest number in $$$[pos_2]$$$, where $$$k = \min(60, m) = \min(60, 1) = 1$$$.

Note that the example is only for understanding the statement and does not guarantee finding the unique permutation $$$p$$$.

Top-K Tracker (Hard Version)

Examples