Description

Mingyue has thought of an integer sequence $a$ of length $n$, which has already been determined. For each index $1 \leq i \leq n$, $\lvert a_i \rvert \leq 10^6$ holds.

Mingyue has only told the value of $n$ to Qingfeng, and he can ask up to $10^4$ queries. In each query, Qingfeng picks an interval $[l, r]$ (which must satisfy $1 \leq l \leq r \leq n$), then Mingyue will multiply $a_i$ by $-1$ for each $l \leq i \leq r$. After the multiplications are processed, Mingyue will tell Qingfeng the current Greatest Subsegment Sum$^\dagger$ of the array $a$. Note that the queries are permanent.

Qingfeng can only make one answer, in which he must recover the initial array $a_1, \ldots, a_n$. Suppose you are Qingfeng, please finish the game.

$\dagger$: The Greatest Subsegment Sum of an array $a$ is defined as the maximum value of the sum of any subsegment (possibly, an empty subsegment) of $a$.

Interaction

To ask a question, output a line in the following format:

• $?\;l\;r$ — to pick an interval $[l, r]$ and query. You should guarantee that $1 \leq l \leq r \leq n$.

The jury will output a single integer $M$ denoting the current Greatest Subsegment Sum, after processing your query.

When you have determined the initial array, output a line in the following format:

• $!\;a_1\;a_2\;\ldots\;a_n$. You should guarantee that $\lvert a_i \rvert \leq 10^6$.

After printing a query, do not forget to output the end of the line and flush the output. Otherwise, you will get an arbitrary verdict except Accepted. To do this, use:

• fflush(stdout) for C/C++；
• std::cout << std::flush for C++;
• System.out.flush() for Java;
• stdout.flush() for Python;
• flush(output) for Pascal;
• see the documentation for other languages.

Specially, the output will be automatically flushed if you use std::endl to print an end-of-line, for C++.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $t$. The description of the test cases follows.

The first line of each test case contains a single integer $n$ — the length of the array $a$.

After reading $n$, you should interact with the jury with respect to the Interaction section above.

• If the initial value of $a_1, \ldots, a_n$ is reported wrong, or you have exceeded the limit of queries, the jury immediately terminates and you will receive $0$ points.
• Otherwise, if this is the last test case, the jury terminates you will receive points according to the maximum number of queries you have made in each test case.
• Otherwise, the interaction continues.

Output Format

Refer to the Interaction and Input section above.

1
5

3

2

? 1 3

? 1 3

! 1 -1 0 2 -2

Hint

Sample Description

Note that the example test cases do not represent an optimal strategy for asking questions and are only shown for the sake of demonstrating the interaction format. Specifically, we cannot uniquely determine the initial array $a$ in the examples.

Constraints

Subtasks are used in this problem.

• Subtask 1 (20 pts): $n \leq 13$.
• Subtask 2 (80 pts): No additional constraints.

For each test data, it's guaranteed that $1 \leq t \leq 10$, $1 \leq n \leq 10^3$, $\lvert a_i \rvert \leq 10^6$, and the interactor is not adaptive (that means the initial value of $a_1, \ldots, a_n$ has already been determined before all the queries).

Scoring

A Subtask has a positive score (before rounding to integers) if and only if in all test cases, the answers are correct and the number of queries made for each test case does not exceed $10^4$.

Denote the maximum number of queries in all the test cases in a subtask as $Q$. Then the rate of score of the Subtask is calculated as follows:

• $1.0$, if $Q \leq 3\;001$;
• $1.0 - \frac{Q - 3\;001}{100}$, if $3\;001 < Q \leq 3\;011$;
• $0.9 - \frac{Q - 3\;011}{1000}$, if $Q > 3\;011$.

Postscript

"I hope that, in the future, there will always be someone who can tolerate your fragility and listen to your words."

"The breeze of spring, sprung up in your mind, will never be alone."