Final Boss Phase 2 (Lava) / Giant Bowser — Shiho Fujii, Ryo Nagamatsu, New Super Mario Bros. Wii

$\text{[math]}$

This is the hard version of the problem. The difference between the versions is that in this version, $$$n \leq 400$$$ and you may make $$$1500$$$ queries. You can hack only if you solved all versions of this problem.

This is an interactive problem.

Let $$$n$$$ be a positive integer. A function on $$$n$$$ variables $$$x_1, \ldots, x_n$$$ is called min-max if it can be constructed as writing only $$$\min$$$ and $$$\max$$$ calls around $$$x_1, \ldots, x_n$$$ with each variable appearing exactly once in order from left to right in the expression. For example, $$$\min(x_1, x_2, x_3)$$$ is a min-max function on $$$3$$$ variables, but $$$\max(\min(x_1, x_3), x_2)$$$ and $$$\min(\max(x_1, x_2), \max(x_2, x_3))$$$ are not.

Bowser has chosen a min-max function on $$$n$$$ ($$$2 \leq n \leq 400$$$) variables and tells you $$$n$$$. Additionally, he lets you ask queries of the following form: you give Bowser $$$n$$$ integers $$$x_1, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) as input, and he tells you $$$f(x_1, \ldots, x_n)$$$.

To escape his castle, you have to deduce his function using at most $$$1500$$$ queries in total. After that, to prove to him that you have learned the function, Bowser will give you up to $$$5000$$$ of his own inputs $$$x_1, \ldots, x_n$$$, to which you must respond with the correct value of $$$f(x_1, \ldots, x_n)$$$.

Since Bowser's castle is very secure, he actually has multiple functions for you to figure out, with a total variable count of at most $$$400$$$. Additionally, he constrains that you use at most $$$1500$$$ queries across all of the functions and that he will also not ask more than $$$5000$$$ queries in total.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 400$$$) — the number of variables in the min-max function.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$400$$$.

After you read this line of input, the interaction begins with your first query.

Interaction

To make a query, output a line (without quotes) in the following format:

"? $$$x_1$$$ $$$x_2$$$ $$$\ldots$$$ $$$x_n$$$" ($$$1 \leq x_i \leq 10^9$$$).

Then, after each query, read a single integer — the answer to your query. You can make up to $$$1500$$$ queries of this type in total across all $$$t$$$ test cases.

Once you are ready to begin answering Bowser's queries, output a line containing a single character "!" (without quotes).

Each of Bowser's queries contains a single line of $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) — Bowser's input. It is guaranteed that Bowser will not make more than $$$5000$$$ queries in total across all $$$t$$$ test cases.

After each query, output a single integer — the value of $$$f(x_1, x_2, \ldots, x_n)$$$. Note that these queries are online, so Bowser will only provide you the next query after you respond to his previous query.

Once Bowser is done asking queries, you will receive a single line containing the integer $$$0$$$. After this, proceed to the next test case or exit if this is the last test case.

The interactor in this task is partially adaptive. In particular, the functions Bowser chooses are fixed at the beginning of each interaction, but his queries to you may change.

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 reveive 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 200$$$) — the number of test cases.

The first line of each test case should contain a single integer $$$n$$$ ($$$2 \leq n \leq 400$$$) — the number of variables in the min-max function.

The second line of each test case should contain a series of space-separated tokens (without quotes) from the following list, specifying the min-max function:

"min"
"max"
"("
")"
","
positive integers in the range $$$1, 2, \ldots, n$$$.

The sum of $$$n$$$ over all test cases should not exceed $$$400$$$.

For instance, the hack case corresponding to the example input is as follows:

2
3
max ( 1 , 2 , 3 )
4
min ( max ( 1 , 2 ) , max ( 3 , 4 ) )

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

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

Note

In the first test case, Bowser's min-max function is $$$f := \max(x_1, x_2, x_3)$$$. After asking two queries to receive $$$f(5, 4, 3) = 5$$$ and $$$f(1, 2, 1) = 2$$$ from the jury, the solution is ready to answer the jury's queries. It correctly deduces that $$$f(3, 6, 2) = 6$$$ and $$$f(3, 5, 7) = 7$$$.

In the second test case, Bowser's min-max function is $$$f := \min(\max(x_1, x_2), \max(x_3, x_4))$$$. After asking two queries to receive $$$f(1, 9, 8, 7) = 8$$$ and $$$f(5, 10^9, 2, 3) = 3$$$ from the jury, the solution is ready to answer the jury's queries. It correctly deduces that $$$f(8, 7, 6, 5) = 6$$$.

Note that it is not guaranteed that the queries in the example uniquely determine the min-max function. The example is there only to demonstrate how the queries work. Empty lines in the example input and output are given only for better readability; you don't need to output them in your solution.

Bowser's Castle (Hard Version)

Examples