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$.