M. MEX Queries
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden array $$$a$$$ of size $$$n$$$.

You can make queries of the following form:

  • Provide a subset $$$P \subseteq \{1, 2, ..., n\}$$$ and a subset $$$Q \subseteq \{0, 1, 2, ..., n\}$$$.
  • The interactor will construct a set $$$S = \{a_{p_i} \mid p_i \in P\} \cup Q$$$. It will calculate and give you the MEX$$$^†$$$ of the set $$$S$$$.

Using at most $$$15 n$$$ queries, find the hidden array $$$a$$$ and output it.

$$$^†$$$The MEX of a set is the smallest non-negative integer that is not present in the set. For example, MEX($$$\{0, 1, 4, 5\}$$$) is $$$2$$$ and MEX($$$\{45\}$$$) is $$$0$$$.

Input

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 400$$$) — the size of the hidden array $$$a$$$ (although they will not be provided in the input, the elements of $$$a$$$ satisfy $$$0 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$400$$$.

Interaction

You can make queries in the following format — to query subsets $$$P$$$ and $$$Q$$$, output one line of the form "? $$$x$$$ $$$y$$$" (where $$$x = |P|$$$ and $$$y = |Q|$$$). On the next line, output $$$x$$$ unique space-separated integers — the elements of $$$P$$$. On the next line, output $$$y$$$ unique space-separated integers — the elements of $$$Q$$$. After that, read a single integer — the value of MEX of $$$S$$$ (which is constructed as described above).

To report the hidden array as $$$b$$$, output "! $$$b_1$$$ $$$b_2$$$ ... $$$b_n$$$". Then, the interaction continues with the next test case.

Reporting the answer does not count towards the number of queries made.

Note that you have to use the flush operation right after printing each line — otherwise you may get Idleness Limit Exceeded verdict. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().

Example
Input
3
# Test case 1
1
1

# Test case 2
6
3
0

# Test case 3
8
0
Output
# Test case 1
? 1 0
1

! 0

# Test case 2
? 3 1
2 6 4
0
? 3 3
5 3 1
4 5 6
! 3 1 4 2 5 0

# Test case 3
? 8 1
1 2 3 4 5 6 7 8
8
! 8 8 8 8 8 8 8 8
Note

You do not have to handle comments (lines starting with #) in the input; they are only for presentation purposes and will not be present in the test cases.

The queries given in the sample input and output are for demonstrating the interaction, and may not logically lead to a correct output.

  • Test case 1: The hidden array is $$$[0]$$$.

    The participant's code makes one query, with $$$P = \{1\}$$$ and $$$Q = \{\}$$$. The interactor calculates $$$S = \{0\}$$$ and returns its MEX, $$$1$$$.

    The participant's code correctly concludes that the hidden array is $$$[0]$$$ and outputs it.

  • Test case 2: The hidden array is $$$[3, 1, 4, 2, 5, 0]$$$.

    The participant's code makes the first query query, with $$$P = \{2, 6, 4\}$$$ and $$$Q = \{0\}$$$. The interactor calculates $$$S = \{1, 0, 2\}$$$ and returns its MEX, $$$3$$$.

    The participant's code makes the second query, with $$$P = \{5, 3, 1\}$$$ and $$$Q = \{4, 5, 6\}$$$. The interactor calculates $$$S = \{5, 4, 3, 6\}$$$ and returns its MEX, $$$0$$$.

    The participant's code correctly concludes that the hidden array is $$$[3, 1, 4, 2, 5, 0]$$$ and outputs it.