Interactive Manhattan Points Reconstruction

This is an interactive problem.

On a plane, there are \( k \) distinct grid points with integer coordinates, where both the x‐coordinate and the y‐coordinate lie in \( [-b,b] \). In each query, you can specify at most \(2000\) (denoted as \( d \)) distinct grid points. The interactive judge will then return a multiset of \( kd \) Manhattan distances (in non-decreasing order) between every queried point and each of the \( k \) hidden points.

The Manhattan distance between two points \( (x_1,y_1) \) and \( (x_2,y_2) \) is defined as \[ |x_1-x_2|+|y_1-y_2|, \] where \(|\cdot|\) denotes the absolute value.

You are allowed to make at most \( w \) queries, and the total number of queried points (i.e. the sum of all \( d \) across queries) must not exceed \(2\times10^4\). Using the responses from your queries, you must determine all \( k \) hidden points. When you are ready, output the \( k \) points in any order.

Interaction Format

• Initially, your program reads a line with three positive integers \( b,\, k,\, w \).
• You may then issue at most \( w \) queries. Each query should be formatted as follows:
  ? s_1 t_1 s_2 t_2 \cdots s_d t_d
  where the queried points are \( (s_1,t_1), (s_2,t_2), \dots, (s_d,t_d) \). You must ensure that \( -10^8 \le s_i,t_i \le 10^8 \), \( d \le 2000 \), and all queried points in one query are distinct. Moreover, the total \( d \) over all queries must be at most \(2\times10^4\).
• After each query, read a line containing \( kd \) non-negative integers in non-decreasing order. These represent the Manhattan distances between every queried point and the hidden points.
• Once you have determined the \( k \) hidden points \( (x_1,y_1), (x_2,y_2), \dots, (x_k,y_k) \), output them in one line as:
  ! x_1 y_1 x_2 y_2 \cdots x_k y_k
  You may output the points in any order.
• After each query and your final answer, make sure to flush the output buffer.

Note: In this problem, you are not required to actually perform the queries. For the purpose of offline testing, the input will include the hidden points after the initial line, and your program should simply read them and output the answer correctly.

inputFormat

The input starts with a line containing three positive integers \( b,\, k,\, w \), where \( b \) is the bound for the coordinates, \( k \) is the number of hidden points, and \( w \) is the maximum number of queries allowed.

For offline testing purposes, the next line will contain \( 2\times k \) integers representing the coordinates of the hidden points: \( x_1\ y_1\ x_2\ y_2\ \cdots\ x_k\ y_k \). Each coordinate satisfies \( -b \leq x_i, y_i \leq b \).

Any additional lines simulate the interactive responses and can be ignored in your solution.

outputFormat

Output a single line containing ! followed by \( 2\times k \) integers representing the coordinates of the hidden points. The points can be output in any order.

Example:

! x1 y1 x2 y2 ... xk yk

sample

10 1 1
0 0

! 0 0

</p>