Problem B
Quark Microscopy

Disaster has struck! Niels’ precious pet atom has been hit by a cosmic ray, and split up into a mass of individual quarks. Niels is now desperate to find the quarks and piece them together again, and has turned to you for help.

The $N$ quarks are located along a $1$ meter (${10}^{18}$ attometers) long line. To your aid you have a very precise (but somewhat quirky) quark microscope, which is able to detect and measure distances to nearby quarks. Due to quantum effects, it cannot directly tell you the location of the nearest quark to a measured position. Instead, it tells you the distance to the second closest! It also determines the number of quarks at that distance.

To be more precise: you can make measurements at integer positions $x$ along the line. For each measurement, the distances $d_1,d_2,\dots ,d_n$ from $x$ to all the quarks will be determined, sorted in increasing order, and you will be given $d_2$, along with the number of indices $i$ such that $d_i=d_2$ (which will be either $1$ or $2$). After performing enough measurements, you should answer with the positions of all the quarks.

Each quark has an integer position between $1$ and ${10}^{18}$ attometers, counting from the start of the line. No two quarks will occupy the same position (as per the Pauli exclusion principle).

Depending on the number of measurements performed, your program will receive different amounts of points.

Interaction

Your program will interact with the judge by reading from standard in and writing to standard out. First, the judge will output a line containing the number of quarks $N$ ($3\le N\le 100$) and the number of the test group $T$ ($1\le T\le 3$).

Then, your program can make queries of the following forms:

• ? x ($-{10}^{18}\le x\le 2\cdot {10}^{18}$): find the distance to the second closest quark to $x$. The judge will respond with two space-separated numbers $r$, $m$, where $r$ is the distance to the second closest quark, and $m$ is the number of quarks at that distance (either $1$ or $2$).

• ! $a_1$ $a_2$ $\dots$ $a_n$: guess the positions of the quarks ($1\le a_i\le {10}^{18}$). $a_1,a_2,\dots ,a_n$ may be given in any order. No additional queries should be made after this.

After each query, you should make sure to flush standard output before reading the judge’s response, or your solution may end up graded as Time Limit Exceeded. In Python this happens automatically, and in C++ it happens when using cout << endl; to print a newline. In C you can use fflush(stdout); after printf.

If you make an invalid query, your program may receive either Wrong Answer or Run Time Error.

To facilitate testing of your solution, we provide a simple tool that you can download from the sidebar of the Kattis page for this problem. See the comment at the top of the file for a description of how to use it.

Scoring

Your solution will be tested on a set of test groups, each worth up to a number of points. To get the points for a test group you need to solve all test cases in the test group.

For each test group, let $Q$ be the maximum number of ?-type queries used across any test case in that group. Then for that group $r$ is defined according to the following table:

 3 3

 ? 5

 6 1

 ? 15

 4 1

 ? 11

 1 2

 ! 11 10 12

 3 1

 ? 1

 2 1

 ? 2

 1 2

 ? 3

 2 1

 ? 47

 45 1

 ! 1 3 92