Model E

The Tesla Model E - Space X's newest Mars Rover - has just landed on the Red Planet, in a crater near the base of Mount Olympus. Its goal is to locate the base of the mountain.

The surface of the planet is seen as a square grid of dimension N, each cell having associated some altitude. The base of the mountain is the only cell that has altitude 0 (it is guaranteed that exactly one such cell exists). The Model E has the capacity to scan the altitude of the Martian landscape at any coordinates (i, j), 0 ≤ i, j < N. Moreover, the grid ascends on both axes: Ai,j < Ai+1,j and Ai,j < Ai,j+1, ∀ i, j ≥ 0.

However, each scan drains a lot of energy, so the total number of scanned cells should be as small as possible. You decide where to make the scans.

Interaction

Your solution will be verified by a simulator. The two programs interact as follows:

Your programs begins by printing two integers X Y. The verifier will respond with the altitude of cell (X, Y). If this altitude is 0, your program can halt. Otherwise, it should repeat the process, trying another cell. In case of invalid coordinates, you will receive an Invalid Query verdict.

Note: After each command you should print a newline character and immediately flush the output, using functions such as `fflush(stdout)` or `cout.flush()`.

Score

Your solution is considered correct if it manages to correctly identify the cell with an altitude of 0, under the time constraint. In this case, your score for a certain testcase will be computed with the following formula:

FLOOR(MIN(25, 25 * (OFFICIAL SOLUTION'S NUMBER OF QUERIES) / (YOUR NUMBER OF QUERIES)))

Your final score will be equal to the sum of scores for each testcase. If your solution does not find the answer (or gets a TLE verdict), your score for that testcase will be 0. However, it will not affect other cases.

Note: the maximum score for pretests is 30.

Constraints

• N = 200 for all tests.

Example interaction

User programVerifierGrid
0 0
-5
```-5 ? ? ? . . . ?
? ? ? ? . . . ?
? ? ? ? . . . ?
? ? ? ? . . . ?
. . . . .
. . . .   .
. . . .     .
? ? ? ?       ?
```
0 1
-3
```-5 -3 ? ? . . . ?
?  ? ? ? . . . ?
?  ? ? ? . . . ?
?  ? ? ? . . . ?
.  . . . .
.  . . .   .
.  . . .     .
?  ? ? ?       ?
```
1 0
-1
```-5 -3 ? ? . . . ?
-1  ? ? ? . . . ?
?  ? ? ? . . . ?
?  ? ? ? . . . ?
.  . . . .
.  . . .   .
.  . . .     .
?  ? ? ?       ?
```
2 1
8
```-5 -3 ? ? . . . ?
-1  ? ? ? . . . ?
?  8 ? ? . . . ?
?  ? ? ? . . . ?
.  . . . .
.  . . .   .
.  . . .     .
?  ? ? ?       ?
```
1 2
1
```-5 -3 ? ? . . . ?
-1  ? 1 ? . . . ?
?  8 ? ? . . . ?
?  ? ? ? . . . ?
.  . . . .
.  . . .   .
.  . . .     .
?  ? ? ?       ?
```
1 1
0
```-5 -3 ? ? . . . ?
-1  0 1 ? . . . ?
?  8 ? ? . . . ?
?  ? ? ? . . . ?
.  . . . .
.  . . .   .
.  . . .     .
?  ? ? ?       ?
```
*stops execution*
Questions?