E. Monotone Subsequence
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

Faker is being naughty again. You asked him to create a nice query problem, but he created an interactive problem where he is answering a query instead! Faker hid a permutation from you, and you have to infer some interesting information by interacting with him.

You are given an integer $$$n$$$. Faker hid a hidden permutation$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_{n^2+1}$$$ of length $$$n^2+1$$$. Your goal is to find a monotone subsequence (either increasing or decreasing) of the hidden permutation, with length exactly $$$n+1$$$. It can be proved that every permutation of length $$$n^2 + 1$$$ contains a monotone subsequence of length $$$n+1$$$. For more information about the proof, you can check out this Wikipedia page.

To find it, you can make at most $$$n$$$ skyscraper queries to the interactor, which is defined as follows:

  • You provide a set of $$$k$$$ indices as a strictly increasing sequence: $$$i_1, i_2, \ldots, i_k$$$.
  • The interactor considers the values of the hidden permutation at these indices: $$$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$$$.
  • The interactor then returns the indices corresponding to the visible skyscrapers from this set. An index $$$i_j$$$ is visible if its value $$$p_{i_j}$$$ is greater than the values of all preceding elements in your query, i.e., $$$p_{i_j} \gt p_{i_m}$$$ for all $$$1 \le m \lt j$$$. This is equivalent to finding the indices of the left-to-right maxima of the sequence $$$(p_{i_1}, \ldots, p_{i_k})$$$.

After making at most $$$n$$$ queries, you must report a valid monotone subsequence of length exactly $$$n+1$$$.

Note that the permutation $$$p$$$ is fixed before any queries are made and does not depend on the queries.

$$$^{\text{∗}}$$$A permutation of length $$$m$$$ is an array consisting of $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$m=3$$$ but there is $$$4$$$ in the array).

Input

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

It is guaranteed that the sum of $$$n^2+1$$$ over all test cases does not exceed $$$10\,001$$$.

Interaction

The interaction for each test case begins by reading the integer $$$n$$$.

To make a query, print a line in the following format:

  • ? $$$k \; i_1 \; i_2 \; \ldots \; i_k$$$
where $$$k$$$ is the number of indices in your query ($$$1 \le k \le n^2+1$$$), and $$$i_1, \ldots, i_k$$$ are the indices themselves, satisfying $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n^2+1$$$. The indices should be presented in sorted order.

In response, the interactor will print a line in the following format:

  • $$$c \; j_1 \; j_2 \; \ldots \; j_c$$$

where $$$c$$$ is the number of visible skyscrapers from your query ($$$1 \le c \le k$$$), and $$$j_1, \ldots, j_c$$$ are their indices, satisfying $$$1 \le j_1 \lt j_2 \lt \ldots \lt j_c \le n^2+1$$$. The indices will be presented in sorted order.

To report your final answer, print a line in the following format:

  • ! $$$s_1 \; s_2 \; \ldots \; s_{n+1}$$$
where $$$s_1, \ldots, s_{n+1}$$$ are the indices of the elements that form your found monotone subsequence of length $$$n+1$$$, satisfying $$$1 \le s_1 \lt s_2 \lt \ldots \lt s_{n+1} \le n^2 + 1$$$. The indices should be presented in sorted order.

Note that answering does not count toward your limit of commands.

After printing the answer, your program should proceed to the next test case or terminate if there are no more.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \leq t \leq 5000$$$).

The first line of each test case should contain a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$).

The second line of each test case should contain $$$n^2+1$$$ space separated integers $$$p_1,p_2,\ldots,p_{n^2+1}$$$ ($$$1 \leq p_i \leq n^2+1$$$). $$$p$$$ should be a permutation of length $$$n^2+1$$$.

The sum of $$$n^2+1$$$ should not exceed $$$10\,001$$$.

For example, the following is the hack format of the example test: 

2
1
1 2
2
5 3 4 1 2

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2
1

2 1 2

2

1 1

2 2 3
Output


? 2 1 2

! 1 2

? 3 1 2 3

? 3 2 3 5

! 1 3 4
Note

For the first test case, $$$n=1$$$. The hidden permutation is $$$p=[1, 2]$$$.

  • For the query ? 2 1 2, the visible skyscrapers are at indices $$$1$$$ and $$$2$$$. The interactor returns 2 1 2.
  • An increasing subsequence of length $$$2$$$ at indices $$$1, 2$$$ is reported.

For the second test case, $$$n=2$$$. The hidden permutation is $$$p=[5, 3, 4, 1, 2]$$$.

  • For the query ? 3 1 2 3, the visible skyscraper is at index $$$1$$$. The interactor returns 1 1.
  • For the query ? 3 2 3 5, the visible skyscrapers are at indices $$$2$$$ and $$$3$$$. The interactor returns 2 2 3.
  • A decreasing subsequence of length $$$3$$$ at indices $$$1, 3, 4$$$ is reported.

Although Faker will play the role of interactor, the interactor will never lie to you.