Mineral deposits

Time limit2sMemory limit1024 MB

Summary

Locate k hidden deposits in a grid of half-width b using probe waves that return Manhattan distances, with as few waves as possible.

Level: Hard8 of 10
Topics: Math, Geometry, Implementation
Solved: No attempts yet

Problem

You handle signal processing for an extra-terrestrial mining company. Your vessel is approaching an asteroid. Preliminary scans show $k$ mineral deposits on the asteroid, but their exact locations are unknown.

The surface of the asteroid is a grid of integer coordinates. The $i$ th deposit is at unknown integer coordinates $(x_i, y_i)$ with $-b \le x_i \le b$ and $-b \le y_i \le b$ , for some integer $b$ that corresponds to the size of your initial scan.

To find the exact locations, you may send probes to the surface. Probes are sent out in waves of several probes at once.

Suppose you send a wave of $d$ probes to coordinates $(s_j, t_j)$ for $1 \le j \le d$ . When a probe arrives, it measures the Manhattan distance to each of the $k$ deposits and sends the distances back to the ship. All data packets arrive at the same time, and you cannot tell which probe returned which distance. So the wave returns the $k \cdot d$ integer distances

$|x_i - s_j| + |y_i - t_j| \qquad \text{for all } i \in \{1, \ldots, k\} \text{ and } j \in \{1, \ldots, d\}.$

You need to minimise the number of waves of probes sent to the surface.

Constraints

We always have $1 \leq b \leq 10^8$ , $1 \leq k \leq 20$ , and $2 \leq w \leq 10^4$ .

Examples1

Example 1

Input

4 2 10

2 4 4 4 6 10

0 3 5 8

Expected output


? -4 -3 -1 0 2 -1

? 1 2 0 -2

! 1 2 -3 -2