Guess two numbers
Contest: Codeforces Round 497 (Div. 1)
Difficulty rating: 3000
Tags: binary search, interactive

This is an interactive problem.

Vasya and Vitya play a game. Vasya thought of two integers $$$a$$$ and $$$b$$$ from $$$1$$$ to $$$n$$$ and Vitya tries to guess them. Each round he tells Vasya two numbers $$$x$$$ and $$$y$$$ from $$$1$$$ to $$$n$$$. If both $$$x=a$$$ and $$$y=b$$$ then Vitya wins. Else Vasya must say one of the three phrases:

1. $$$x$$$ is less than $$$a$$$;
2. $$$y$$$ is less than $$$b$$$;
3. $$$x$$$ is greater than $$$a$$$ or $$$y$$$ is greater than $$$b$$$.

Vasya can't lie, but if multiple phrases are true, he may choose any of them. For example, if Vasya thought of numbers $$$2$$$ and $$$4$$$, then he answers with the phrase $$$3$$$ to a query $$$(3, 4)$$$, and he can answer with the phrase $$$1$$$ or phrase $$$3$$$ to a query $$$(1, 5)$$$.

Help Vitya win in no more than $$$600$$$ rounds.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — the upper limit of the numbers.

Interaction format:
First, you need to read the number $$$n$$$, after that you can make queries.

To make a query, print two integers: $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$), then flush the output.

After each query, read a single integer $$$ans$$$ ($$$0 \leq ans \leq 3$$$).

If $$$ans > 0$$$, then it is the number of the phrase said by Vasya.

If $$$ans = 0$$$, it means that you win and your program should terminate.

If you make more than $$$600$$$ queries or make an incorrect query, you will get Wrong Answer.

Your solution will get Idleness Limit Exceeded, if you don't print anything or forget to flush the output.

To flush you need to do the following right after printing a query and a line end:

- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- For other languages see documentation.

Hacks format

For hacks, use the following format:

In the first line, print a single integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — the upper limit of the numbers.

In the second line, print two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq n$$$) — the numbers which Vasya thought of.

In the third line, print a single integer $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — the number of instructions for the interactor.

In each of the next $$$m$$$ lines, print five integers: $$$x_i$$$, $$$y_i$$$, $$$r^{12}_i$$$, $$$r^{13}_i$$$, and $$$r^{23}_i$$$ ($$$1 \leq x_i, y_i \leq n$$$), where $$$r^{ST}_i$$$ equals to either number $$$S$$$ or number $$$T$$$.

While answering the query $$$x\,\, y$$$, the interactor finds a number $$$i$$$ from $$$1$$$ to $$$n$$$ with the minimal value $$$|x-x_i| + |y-y_i|$$$. If multiple numbers can be chosen, the least $$$i$$$ is preferred. Then the interactor answers to the query, but if there are two phrases $$$S$$$ and $$$T$$$ that can be given, then $$$r^{ST}_i$$$ is chosen.

For example, the sample test data file contains the following:

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's analyze the sample test. The chosen numbers are $$$2$$$ and $$$4$$$. The interactor was given two instructions.

For the query $$$(4, 3)$$$, it can return $$$2$$$ or $$$3$$$. Out of the two instructions the second one is chosen, so the interactor returns $$$a^{23}_2=3$$$.

For the query $$$(3, 4)$$$, it can return only $$$3$$$.

For the query $$$(3, 3)$$$, it can return $$$2$$$ or $$$3$$$. Out of the two instructions the first one is chosen (since in case of equal values, the least number is preferred), so the interactor returns $$$a^{23}_1=2$$$.

For the query $$$(1, 5)$$$, it can return $$$1$$$ or $$$3$$$. Out of the two instructions the first one is chosen, so the interactor returns $$$a^{13}_1=1$$$.

In the fifth query $$$(2, 4)$$$, the numbers are guessed correctly, the player wins.

Example input:
5
3
3
2
1
0

Example output:
4 3
3 4
3 3
1 5
2 4

Editorial:
First solution:
Let's keep the set of possible answers as a union of three rectangles forming an angle: $$$A = \left[ x_l, x_m \right) \times \left[ y_l, y_m \right)$$$, $$$B = \left[ x_l, x_m \right) \times \left[ y_m, y_r \right)$$$ and $$$C = \left[ x_m, x_r \right) \times \left[ y_l, y_m \right)$$$, where $$$x_l < x_m \leq x_r$$$ and $$$y_l < y_m \leq y_r$$$. Let $$$S_A$$$, $$$S_B$$$ and $$$S_C$$$ be their areas. We will denote such state as $$$(x_l, x_m, x_r, y_l, y_m, y_r)$$$. The initial state is $$$(0, n + 1, n + 1, 0, n + 1, n + 1)$$$.
Now there are three cases.
1. $$$S_B \leq S_A + S_C$$$ and $$$S_B \leq S_A + S_B$$$, then we will make a query $$$\left( \left\lfloor \frac{x_l + x_m}{2} \right\rfloor, \left\lfloor \frac{y_l + y_m}{2} \right\rfloor \right)$$$.
2. If $$$S_B > S_A + S_C$$$, we will make a query $$$\left( \left\lfloor \frac{x_l + x_m}{2} \right\rfloor, y_m \right)$$$.
3. Finally, if $$$S_C > S_A + S_B$$$, we will make a query $$$\left( x_m, \left\lfloor \frac{y_l + y_m}{2} \right\rfloor \right)$$$.
In case of every response to every query, the new set of possible answers will also form an angle.
Now we want to prove that the area of the angle decreases at least by a quarter every two requests.
In case (1) if the answer is $$$1$$$, then we move to a state $$$\left( \left\lfloor \frac{x_l + x_m}{2} \right\rfloor + 1, x_m, x_r, y_l, y_m, y_r \right)$$$. We cut off at least half of $$$A$$$ and at least half of $$$B$$$. But $$$\frac{S_A}{2} + \frac{S_B}{2} = \frac{S_A + S_B}{4} + \frac{S_A + S_B}{4} \geq \frac{S_A + S_B}{4} + \frac{S_C}{4} = \frac{S_A + S_B + S_C}{4}$$$. I.e. We have cut off at least a quarter already within just one request. If the answer is $$$2$$$, the situation is similar. Finally, if the answer is $$$3$$$, then we move to a state $$$\left( x_l, \left\lfloor \frac{x_l + x_m}{2} \right\rfloor, x_r, y_l, \left\lfloor \frac{y_l + y_m}{2} \right\rfloor, y_r \right)$$$. We cut off at least quarter of $$$A$$$, at least half of $$$B$$$ and at least half of $$$C$$$. But $$$\frac{S_A}{4} + \frac{S_B}{2} + \frac{S_C}{2} \geq \frac{S_A}{4} + \frac{S_B}{4} + \frac{S_C}{4} = \frac{S_A + S_B + S_C}{4}$$$. We also have cut off at least a quarter within just one request. Thus in case (1) we cut off at least a quarter within one request.
In case (2) if the answer is $$$1$$$, then we move to a state $$$\left( \left\lfloor \frac{x_l + x_m}{2} \right\rfloor + 1, x_m, x_r, y_l, y_m, y_r \right)$$$. We cut off at least half of $$$A$$$ and at least half of $$$B$$$. But $$$\frac{S_A}{2} + \frac{S_B}{2} \geq \frac{S_B}{2} \geq \frac{S_B}{4} + \frac{S_B}{4} \geq \frac{S_B}{4} + \frac{S_A + S_C}{4} = \frac{S_A + S_B + S_C}{4}$$$. We have cut off at least a quarter within just one request. If the answer is $$$2$$$, then we move to a state $$$(x_l, x_r, x_r, y_m + 1, y_r, y_r)$$$. But then if will be case (1), thus we will cut off at least a quarter with the next request. Finally, if the answer is $$$3$$$, then we move to a state $$$\left( x_l, \left\lfloor \frac{x_l + x_m}{2} \right\rfloor, x_r, y_l, y_m, y_r \right)$$$. We cut off at at least half of $$$B$$$. But $$$\frac{S_B}{2} \geq \frac{S_B}{4} + \frac{S_B}{4} \geq \frac{S_B}{4} + \frac{S_A + S_C}{4} = \frac{S_A + S_B + S_C}{4}$$$. We also have cut off at least a quarter within just one request.
Case (3) is similar to case (2).
Thus the maximal number of requests will be no more than $$$1 + 2 * \log_{4/3} \left( \left( 10^{18} \right)^2 \right) \approx 577$$$.
Second solution:
Let's keep the set of possible answers in form of a ladder $$$A$$$. Then lets find minimal $$$X$$$ such that $$$S \left( A \cap \{x \leq X\} \right) \geq \frac{S(A)}{3}$$$. And lets find minimal $$$Y$$$ such that $$$S \left( A \cap \{y \leq Y\} \right) \geq \frac{S(A)}{3}$$$. Then $$$$$$ S \left( A \cap \{x \geq X\} \cap \{y \geq Y\} \right) = S \left( A \setminus \left( A \cap \{x \leq X - 1\} \right) \setminus \left( A \cap \{y \leq Y - 1\} \right) \right) \geq $$$$$$ $$$$$$ \geq S(A) - S \left( A \cap \{x \leq X - 1\} \right) - S \left( A \cap \{y \leq Y - 1\} \right) \geq S(A) - \frac{S(A)}{3} - \frac{S(A)}{3} = \frac{S(A)}{3}. $$$$$$ I.e. we cut off at least third of the area of the ladder on each request.
Thus the maximal number of requests will be no more than $$$1 + \log_{3/2} \left( \left( 10^{18} \right)^2 \right) \approx 205$$$.