E2. Mexness (Hard Version)

*This is the hard version of the problem. The only difference is the maximum number of queries.* *This is an interactive problem.* There is a secret permutation $p_0, p_1, \\dots, p_{n -1}$, which is a permutation of ${0, 1, \\dots, n -1}$. There is also a variable $m x$. At first, $m x = 4$. Your task is to guess the permutation by using queries of the following type: The $"mex"(a)$ of an array $a$ is defined as the smallest non-negative integer that does not appear in $a$. For example, if $a = [ 0, 1, 2, 4 ]$, then $"mex"(a) = 3$ because $3$ is the smallest non-negative integer not present in $a$. Find out the secret permutation using at most $7 n$ queries of the second type. Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 200$). The description of the test cases follows. The first line of each test case contains one integer $n$ ($2 <= n <= 1024$). It is guaranteed that the sum of $n$ over all test cases will not exceed $1024$. At this moment, the permutation $p_0, p_1, \\dots, p_{n -1}$ is chosen. 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. Then you can make queries. To make a query of the first type, output a line in the format "! $i$ $v$" (without quotes). Note that this line is *not* included in the count of $7 n$ queries of the second type. To make a query of the second type, output a line in the format "? $k$ $j_1$ $j_2$ $\\dots$ $j_k$" (without quotes) ($1 <= k <= n$, $0 <= j_i < n$). After each query, read an integer — the answer to your query. After performing $n$ queries of the first type (in other words, you have guessed the entire permutation $p$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $n$. After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the _Idleness limit exceeded verdict_. To flush, use: In the first test case, the hidden permutation $p$ is $[ 2, 0, 1 ]$. For the query "_? 2 1 0_", the jury returns $1$ because $min (m x, "mex"(p_1, p_0)) = min (4, 1) = 1$. Then, for answer "_! 2 1_", the jury increases $m x$ by $1$ since the answer is correct and you haven't answered for $p_2$ twice. For the query "_? 1 0_", the jury returns $0$ because $min (m x, "mex"(p_0)) = min (5, 0) = 0$. Note queries are only for understanding statements and do *not* guarantee finding a unique permutation $p$. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 200$). The description of the test cases follows. ## Interaction The first line of each test case contains one integer $n$ ($2 <= n <= 1024$). It is guaranteed that the sum of $n$ over all test cases will not exceed $1024$.At this moment, the permutation $p_0, p_1, \\dots, p_{n -1}$ is chosen. 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.Then you can make queries.To make a query of the first type, output a line in the format "! $i$ $v$" (without quotes). Note that this line is *not* included in the count of $7 n$ queries of the second type.To make a query of the second type, output a line in the format "? $k$ $j_1$ $j_2$ $\\dots$ $j_k$" (without quotes) ($1 <= k <= n$, $0 <= j_i < n$). After each query, read an integer — the answer to your query.After performing $n$ queries of the first type (in other words, you have guessed the entire permutation $p$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $n$.After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the _Idleness limit exceeded verdict_. To flush, use: _fflush(stdout)_ or _cout.flush()_ in C++; _System.out.flush()_ in Java; _stdout.flush()_ in Python; see the documentation for other languages. [samples] ## Note In the first test case, the hidden permutation $p$ is $[ 2, 0, 1 ]$.For the query "_? 2 1 0_", the jury returns $1$ because $min (m x, "mex"(p_1, p_0)) = min (4, 1) = 1$.Then, for answer "_! 2 1_", the jury increases $m x$ by $1$ since the answer is correct and you haven't answered for $p_2$ twice.For the query "_? 1 0_", the jury returns $0$ because $min (m x, "mex"(p_0)) = min (5, 0) = 0$.Note queries are only for understanding statements and do *not* guarantee finding a unique permutation $p$.