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

**(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**

`0`**. Moreover, the grid ascends on both axes:**

`(i, j), 0 ≤ i, j < N`**and**

`A`_{i,j}< A_{i+1,j}**.**

`A`_{i,j}< A_{i,j+1}, ∀ i, j ≥ 0However, 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

**. If this altitude is**

`(X, Y)`**, your program can halt. Otherwise, it should repeat the process, trying another cell. In case of invalid coordinates, you will receive an**

`0`**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

for all tests.`N = 200`

### Example interaction

User program | Verifier | Grid |
---|---|---|

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 | |

*stops execution* |

### Solution #1

The obvious approach would be to query the whole matrix, which has a complexity of ** O(N^{2})**. This idea obtains a null score.

1 #!/usr/bin/python2.7 2 import sys 3 4 n = 200 5 for i in range(n): 6 for j in range(n): 7 print "%i %i" % (i, j) 8 sys.stdout.flush() 9 10 if input() == 0: 11 exit(0)

### Solution #2

A better approach is to apply a binary search on each line (or column), which has a complexity of ** O(N * log N)**. This idea obtains

**of the maximum score.**

`~40%`1 #include <iostream> 2 using namespace std; 3 4 const int n = 200; 5 6 int main() { 7 for(int i=0; i<n; i++) { 8 int lo = -1; 9 int hi = n; 10 11 while(hi - lo > 1) { 12 int mid = (hi + lo) / 2; 13 14 cout<<i<<" "<<mid<<"\n"; 15 cout.flush(); 16 17 int val; 18 cin>>val; 19 20 if(val > 0) 21 hi = mid; 22 if(val < 0) 23 lo = mid; 24 if(val == 0) 25 return 0; 26 } 27 } 28 }

### Solution #3

We can solve this problem in linear time (with approximately ** 2*n** queries) by noticing that we can start from the upper right corner of the matrix and moving one step at a time to neighbouring cells, as such:

- if the value in the current cell is
, stop execution.`0` - if it is bigger, go to the left.
- if it is smaller, go down.

This solution obtains ** 80~90%** of the maximum score and can be implemented easily:

1 #!/usr/bin/python3 2 import sys 3 4 i, j = 0, 199 5 while True: 6 print("%i %i" % (i, j)) 7 sys.stdout.flush() 8 9 x = input() 10 11 if x == '0': 12 exit(0) 13 elif '-' in x: 14 i += 1 15 else: 16 j -= 1

### Solution #4

The official solution uses a *divide et impera* approach to find the answer. Assume that the hill looks like this:

We start by taking the middle row of the matrix, and applying a binary search on that row. Once we find the element which is closest to ** 0**, the whole matrix can be split into 4 smaller matrices, like this:

We then apply the same algorithm recursively to the highlighted parts, until we find the element ** 0**.

This solution's complexity is more difficult to compute. In practice, it behaves better than the linear solution. Depending on the implementation, it should obtain the maximum score.