P12399 「FAOI-R9」A Youngsters' Tour

> Even if I can buy laurel wine for you And get afloat, Could our youth renew? > > —— *Liu Guo, Song of More Sugar, Translated by Xu Yuanchong* Qingfeng recalls the day when he had just finished programming syntax and entered the world of algorithms. He was amazed at the elegance of the linear approach to the Greatest Subsegment Sum problem, which doesn't need to enumerate intervals. "Mingyue, can we play a game?"

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

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.

Refer to the **Interaction** and **Input** section above.

**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."