题目描述

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

There are $\mathbf{N}$ kings on an infinite chessboard (two-dimensional grid), located in cells with coordinates $(\mathbf{X}_{1}, \mathbf{Y}_{1})$, $(\mathbf{X}_{2}, \mathbf{Y}_{2})$, ..., $(\mathbf{X}_{\mathbf{N}}, \mathbf{Y}_{\mathbf{N}})$. Both $\mathbf{N}$ and the kings' coordinates are unknown to you. However, you do know the following things:

• $\mathbf{N}$ is at least 1 and at most $\mathbf{N}_{\text{max}}$.
• No king's coordinates (X or Y) have an absolute value exceeding $\mathbf{M}$.
• The $\mathbf{N}$ kings are located in $\mathbf{N}$ different cells.

The kings want to meet in a single cell of the board. If some cell $(\mathbf{X}, \mathbf{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(|\mathbf{X}-\mathbf{X}_{\mathbf{i}}|, |\mathbf{Y}-\mathbf{Y}_{\mathbf{i}}|)$. The total number of moves used by all kings is thus equal to the sum of those maximums over all values of $\mathbf{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 $(\mathbf{A}, \mathbf{B})$ (with each of $\mathbf{A}$ and $\mathbf{B}$ between $-10 \times \mathbf{M}$ and $10 \times \mathbf{M}$, inclusive), and have the judge tell you the total number of moves the kings would use to get there — the sum (over all $\mathbf{i}$) of $\max(|\mathbf{X}_{\mathbf{i}}-\mathbf{A}|, |\mathbf{Y}_{\mathbf{i}}-\mathbf{B}|)$. You can have at most $\mathbf{R}$ such exchanges with the judge, choosing your values of $\mathbf{A}$ and $\mathbf{B}$ each time. Note that the kings do not actually move, so their locations $(\mathbf{X}_{\mathbf{i}}, \mathbf{Y}_{\mathbf{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 $(\mathbf{C}, \mathbf{D})$ (with each of $\mathbf{C}$ and $\mathbf{D}$ between $-10 \times \mathbf{M}$ and $10 \times \mathbf{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 $\mathbf{R}$ such exchanges, and you must correctly respond to all of the judge's requests.

Interactive Protocol

This is an interactive problem.

Initially, your program should read a single line containing four integers $\mathbf{T}$, $\mathbf{N}_{\text{max}}$, $\mathbf{M}$ and $\mathbf{R}$: the number of test cases, the maximum number of kings, the maximum absolute value for any coordinate for any king, and the maximum number of requests per phase, respectively. (Note that the values of $\mathbf{M}$ and $\mathbf{R}$ are fixed, and are provided as input only for convenience; see the Limits section for more details.) Then, you need to process $\mathbf{T}$ test cases.

In each test case, there are two phases. In the first phase, the i-th exchange is as follows:

• Your program sends one line containing two integers $\mathbf{A}_{\mathbf{i}}$ and $\mathbf{B}_{\mathbf{i}}$, representing the x and y coordinates of a cell.
  • Both $\mathbf{A}_{\mathbf{i}}$ and $\mathbf{B}_{\mathbf{i}}$ must be between $-10 \times \mathbf{M}$ and $10 \times \mathbf{M}$, inclusive.
• The judge responds with one line containing a single integer: the total number of moves the kings need to use to get from their unknown locations to your cell.

You may initiate at most $\mathbf{R}$ such exchanges in this phase. If you make more than $\mathbf{R}$ exchanges, or send a request that the judge can not parse or is out of bounds, the judge responds with one line with a single string $\text{ERROR}$.

To end the first phase and switch to the second phase, you must send one line with the string $\text{READY}$ (the case does not matter), to which the judge responds with the first request of the second phase.

In the second phase, the i-th exchange is as follows:

• The judge sends one line containing two integers $\mathbf{C}_{\mathbf{i}}$ and $\mathbf{D}_{\mathbf{i}}$, representing the x and y coordinates of a cell.
  • Each of $\mathbf{C}_{\mathbf{i}}$ and $\mathbf{D}_{\mathbf{i}}$ will be between $-10 \times \mathbf{M}$ and $10 \times \mathbf{M}$, inclusive.
• Your program must respond with one line containing a single integer: the total number of moves the kings would need to use to get to the given cell.

The judge is guaranteed to send at least 1 and at most $\mathbf{R}$ such requests. If you send an answer that is incorrect or unparseable, the judge responds with $\text{ERROR}$ as described above. If you answer all of the requests correctly, the judge sends one line with a single string $\text{DONE}$, at which point your program should initiate the next test case, or terminate with no error if all $\mathbf{T}$ test cases have been handled.

After the judge sends a line with $\text{ERROR}$, it does not send any other output. If your program continues to wait for the judge after receiving $\text{ERROR}$, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

The number and location of the kings, as well as the number and positions of the requests that the judge sends during the second phases, are chosen before any exchanges occur.

输入格式

See Interactive Protocol.

输出格式

See Interactive Protocol.

提示

Sample Interaction

Note that the following sample interaction is for test set 1, in which there is always exactly one king.

  // Suppose that the judge has decided that in the first test case, the king
  // is at the coordinates (1, -2), and the requests will be (5, -1) and
  // (7, 7).
  t, nmax, m, r = readline_int_list()   // Reads 10 1 1000000 1000
  // Our solution decides (for whatever reason) to check (3, 3) first.
  printline 3 3 to stdout
  flush stdout
  result = readline_int()               // Reads 5
  // Our solution now decides (for whatever reason) to check (2, 0).
  printline 2 0 to stdout
  flush stdout
  result = readline_int()               // Reads 2
  // Our solution concludes that the king is at (3, -2), which is consistent
  // with the observed information so far, but unfortunately not correct.
  // Our solution moves on to the request phase.
  printline READY to stdout
  request_line = readline()             // Reads 5 -1
  printline 2 to stdout                 // Wrong answer!
  request_line = readline()             // Reads ERROR
  exit                                  // exits to avoid an ambiguous TLE error

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.

Limits

Note that a program that just makes valid exchanges with the judge (and does no other processing) takes the following time in our environment: ~13 seconds for C++, ~24 seconds for Java, ~19 seconds for Python and Go.

• $1 \leq \mathbf{T} \leq 15$.
• $\mathbf{M} = 10^{6}$.
• $-\mathbf{M} \leq \mathbf{X}_{\mathbf{i}} \leq \mathbf{M}$, for all $\mathbf{i}$.
• $-\mathbf{M} \leq \mathbf{Y}_{\mathbf{i}} \leq \mathbf{M}$, for all $\mathbf{i}$.
• The pairs $(\mathbf{X}_{\mathbf{i}}, \mathbf{Y}_{\mathbf{i}})$ are distinct.
• $-10 \times \mathbf{M} \leq \mathbf{C}_{\mathbf{i}} \leq 10 \times \mathbf{M}$, for all $\mathbf{i}$.
• $-10 \times \mathbf{M} \leq \mathbf{D}_{\mathbf{i}} \leq 10 \times \mathbf{M}$, for all $\mathbf{i}$.
• $\mathbf{R} = 1000$.

Test set 1 (5 Pts, Visible)

• $\mathbf{N}_{\text{max}} = 1$.

Test set 2 (22 Pts, Hidden)

• $\mathbf{N}_{\text{max}} = 10$.