Background

Translated from Nordic Olympiad in Informatics 2022 Quark Microscopy。If you find that the interaction library is broken, please contact the problem porter qvq。

$\texttt{1s,1G}$。

Problem Description

This is terrible! Niels’s beloved atom was hit by cosmic rays and split into many quarks. Niels urgently wants to find these quarks and then put them back together, so he asked you to help.

These $N$ quarks are located on a line segment of length $1$ meter ($10^{18}$ ångström). Luckily, you have a very accurate but somewhat strange quark microscope that can detect and measure nearby quarks. However, due to quantum effects, it cannot directly tell you the position of the quark closest to the measurement point. Instead, it tells you the position of the second-closest quark to the measurement point, as well as how many quarks are tied for being the second-closest.

More precisely, you may perform a measurement at position $x$ on the line segment. For each measurement, the distances from each quark to $x$ are computed and sorted in nondecreasing order as $d_1,d_2,\cdots,d_N$. You are given $d_2$, and the number of indices $i$ such that $d_i=d_2$ (which will only be $1$ or $2$). After making enough measurements, you need to output the position of every quark.

Each quark’s position is a positive integer in $[1,10^{18}]$ (unit: ångström), measured from the start of the segment. Due to the Pauli exclusion principle, no two quarks share the same position。

Input Format

Your program interacts with the interaction library through standard input and output.

The first line contains two positive integers $N,T$, representing the number of quarks and the subtask number.

Then, your program starts interacting with the library:

• ? x: Query the second-farthest quark from $x$. The library returns two integers $r,m$, where $r$ is the distance to the second-farthest quark, and $m$ is the number of quarks whose distance to $x$ equals $r$ (only $1$ or $2$). You must ensure $-10^{18}\le x\le 2\times 10^{18}$.

• ! $a_1$ $a_2$ $\cdots$ $a_N$: Output the quark positions. You may output these positions in any order. After answering, there should be no extra queries. You must ensure $1\le a_i\le 10^{18}$.

Note: During interaction, you must flush the output buffer after each output.
Below are some common ways to flush the buffer in popular languages:

• C++: fflush(stdout) or cout.flush()。In particular, printing a newline using std::endl also flushes the buffer.
• C: fflush(stdout)。

Output Format

See [Input Format].

3 3

6 1

4 1

1 2

? 5

? 15

? 11

! 11 10 12

3 1

2 1

1 2

2 1

45 1

? 1

? 2

? 3

? 47

! 1 3 92

Hint

Constraints

• $3\le N\le 100$；
• $1\le T\le 3$。

Scoring

Here $r$ is a constant. Let $Q$ be the maximum number of queries you make in a subtask. The value of $r$ is given in the table below:

To make local testing easier, we provide testing_tools.py, which can be downloaded from the attachments. For usage instructions, see the header of the file.

Translated by ChatGPT 5