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

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