Problem AB5. GCD 5.0

The problem has nothing to do with GCD :)

Niki has thought of $N$ hidden lines (or linear functions), and you want to find them. Formally, a line $i$ is defined by a pair of coefficients $(a_i, b_i)$ and defines the linear function $f_i(x) = a_i \cdot x + b_i$.

Niki does not like fractions, so all coefficients are integers.

To find the hidden lines, you can ask questions to find the maximum value of any of the lines at a given $x$. As you already understood, Niki does not like fractions, so you can only ask this question for integer values of $x$. Formally, the answer to this question is: $\max_{1 \le i \le N} f_i(x)$.

The problem must still be solvable. In addition to the above conditions, it is guaranteed that each line is maximal for at least 3 integer values $x \in [-10^9; 10^9]$, or in other words, for every line $i$, there are at least 3 values $x \in [-10^9; 10^9]$ for which $f_i(x) \ge f_j(x)$ for all $j \neq i$. Also, there are no two lines with the same $(a_i, b_i)$.

Write a program that uses as few questions as possible and finds the hidden lines!

Constraints

• $1 \le N \le 10^5$
• $|a_i| \le 10^9$ and each $a_i$ is an integer.
• $|b_i| \le 10^{18}$ and each $b_i$ is an integer.

Interaction

The problem is interactive, and you only need to write a solve function with the following signature:

void solve(int n);

This function will be called exactly once with an argument equal to the number of lines. Your implementation can use the following 2 functions:

long long query(int x);
void answer(long long a, long long b);

Using the query(x) function, you can get information about the maximum value of a line at the corresponding $x$. You can only use this function for $x \in [-10^9; 10^9]$.

The answer function must be called exactly $n$ times - once for each found line. The order of calling does not matter.

Your code must not contain a main function, but it may contain any other helper functions, classes, variables, etc. Your code must include the header file gcd5.h.

For local testing, you are provided with a local grader Lgrader.cpp and a copy of the file gcd5.h. You must compile your code together with the local grader to test it. This can be done by placing them in the same folder and using the command:

g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gcd5.cpp Lgrader.cpp -o gcd5.exe

Scoring

For each test, you will receive a certain result, which is calculated as follows:

1. If you make an invalid query, or fail to guess the hidden lines correctly, you will receive a result of 0.
2. Let $Q$ be the total number of questions you have asked.
3. If $Q > 5 \cdot 10^6$, you will receive a result of 0.
4. Otherwise, the result for the corresponding test is: $$\min \left\{ 0.25 + 0.75 \times \left( \frac{4N}{Q} \right)^2, 1.0 \right\}$$

Subtasks

The portion of points for a given subtask is equal to the minimum result of a subtest within it.

Examples

Input 1

2

Output 1

query(1)
4
query(5)
0
query(6)
1
answer(-1, 5)
answer(1, -5)

Note

In this example, $N = 2$ and the hidden lines are $(1, -5)$ and $(-1, 5)$.