Board Meeting timer 60s memory 1024MB

Note that it is not necessary to know anything about the rules of chess to solve this problem.

There are N kings on an infinite chessboard (two-dimensional grid), located in cells with coordinates (X₁, Y₁), (X₂, Y₂), ..., (X_N, Y_N). Both N and the kings' coordinates are unknown to you. However, you do know the following things:

• N is at least 1 and at most N_max.
• No king's coordinates (X or Y) have an absolute value exceeding M.
• The N kings are located in N different cells.

The kings want to meet in a single cell of the board. If some cell (X, Y) were to be chosen as the meeting cell, then in order to get there, the i-th king would use a number of moves equal to the maximum of the absolute values of the differences of coordinates between its cell and the meeting cell: max(|X-X_i|,|Y-Y_i|). The total number of moves used by all kings is thus equal to the sum of those maximums over all values of i. Note that it is not relevant to this problem exactly how the kings move on the board — only the source and destination cells matter, and the number of moves can always be computed using the above formula.

This problem has two phases. In the first phase, you may repeatedly do the following: propose a meeting location (A, B) (with each of A and B between -10×M and 10×M, inclusive), and have the judge tell you the total number of moves the kings would use to get there — the sum (over all i) of max(|X_i-A|,|Y_i-B|). You can have at most R such exchanges with the judge, choosing your values of A and B each time. Note that the kings do not actually move, so their locations (X_i, Y_i) stay the same for all requests within one test case.

In the second phase, the roles are swapped: the judge gives you a meeting cell location (C, D) (with each of C and D between -10×M and 10×M, inclusive), and you must respond with the total number of moves the kings would use to get there, assuming that the kings are in the same locations as in the first phase. There are at most R such exchanges, and you must correctly respond to all of the judge's requests.