F2. Top-K Tracker (Hard Version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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.$$$ InputEach 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. InteractionThe 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. HacksTo 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\}$$$.ExampleInput2
3
2 3
3
2
2
Output
3 2 3 1
2 1 2
! 3 1 2
4 1 1
! 2 1
NoteIn 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$$$.