Description

Gnar bought $n$ water tanks. The capacity of the $i$-th tank is $i$, and for some unknown reason it initially contains $a_i$ ($0 \le a_i \le i$) units of water.

Curious Gnar wants to know how much water is in each tank, but it is clearly impossible to judge by sight. He hopes you can help him solve this problem.

The only operation Gnar can perform for you is: you first choose $i, j$ ($1 \le i, j \le n$), then:

• If $i \neq j$, he pours water from tank $i$ into tank $j$ without spilling a single drop, until either tank $i$ becomes empty or tank $j$ becomes full. Gnar will tell you whether tank $j$ is full after the operation. Note that the effect of pouring water is kept and will not be restored to the state before the operation.
• If $i = j$, Gnar cannot pour a tank into itself, so he will directly tell you whether tank $j$ is currently full.

Gnar will accept at most $20000$ operations. Otherwise, he will think you are making fun of him.

Your task is to use no more than $20000$ operations and the returned results from Gnar to completely determine the initial $a_1, a_2, \ldots, a_n$.

Of course, Gnar will not cheat. The $a_1, a_2, \ldots, a_n$ you need to find already exist before any operations, and are not generated dynamically during the operations.

Input Format

Read a single positive integer $n$ (the number of water tanks) to start the interaction.

Output Format

After you are sure about the answer, output one line in the form ! a1 a2 ... an to end the interaction.

Interaction Format

During the interaction, output one line in the form ? i j $(1 \le i,j \le n)$ to perform one operation. Then you should read a boolean value, the returned value $x$. If $x = 0$, it means tank $j$ is not full; if $x = 1$, it means tank $j$ is full.

All input should be read from standard input, and all output should be written to standard output. After outputting a line, you must flush the buffer, otherwise your submission will be judged as Time Limit Exceeded. Flush methods are:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• In Python, use stdout.flush().
• For other languages, please check the documentation yourself.

If your output format is wrong, or you perform more than $20000$ operations, your submission will be judged as Wrong Answer.

2

0

1

0

? 1 1

? 2 1

? 1 2

! 0 1

Hint

Sample Explanation #1

The sample shows one possible interaction process.

Initially, the two tanks contain $0, 1$ units of water respectively.

In the first operation, since $i = j$, you directly learn $x = 0$, meaning the first tank is not full.

After the second operation, the two tanks contain $1, 0$ units of water respectively, and you learn $x = 1$, meaning the first tank is currently full.

After the third operation, the two tanks contain $0, 1$ units of water respectively, and you learn $x = 0$, meaning the second tank is currently not full.

Note that the exact amounts of water are not told to you, but using the returned value $x$, you can uniquely determine that $a_1 = 0$ and $a_2 = 1$.

Constraints and Notes

This problem uses bundled tests. You must pass all test points in a Subtask to get the score for that Subtask.

• Subtask #1 (8 points): $n = 2$.
• Subtask #2 (17 points): $n \le 10$.
• Subtask #3 (15 points): $n \le 100$.
• Subtask #4 (15 points): $a_i \le 1$.
• Subtask #5 (25 points): $n \le 500$.
• Subtask #6 (20 points): no special constraints.

For all testdata, it is guaranteed that $2 \le n \le 1000$ and $0 \le a_i \le i$.

Translated by ChatGPT 5