This is an interactive problem.

The territory of country P is a square with a side length of $2 \times 10^{12}$. By setting the center of the territory as the origin and establishing a Cartesian coordinate system parallel to the sides of the square, the entire territory of country P is defined by the range $[-10^{12}, 10^{12}] \times [-10^{12}, 10^{12}]$.

There are $N$ lines $y = a_i x + b_i$ in the territory of country P, where $a_i$ and $b_i$ are integers in the range $[-10^4, 10^4]$. However, you do not know the values of $a_i$ and $b_i$. To obtain this information, you can make at most $Q_\text{max}$ queries to the King:

• Provide a point $(x, y)$ on the plane, and the King will tell you the sum of the distances from $(x, y)$ to these $N$ lines.

You need to recover all $N$ lines through these queries.

Implementation Details

You do not need to, and should not, implement the main() function, nor should you read or write any information to any file or standard input/output streams.

You only need to include the header file lines.h and implement the following function:

void solve(int subtask_id, int N);

• This function will be called exactly once.
• The parameter subtask_id represents the subtask ID of the current test case.
• The parameter N is the $N$ described in the problem statement, representing the number of lines.

You can call the following function:

long double query(long double x, long double y);

• The parameters x and y represent the coordinates $P(x, y)$ of the point you are querying.
• You must ensure $x, y \in [-10^{12}, 10^{12}]$.
• This function returns the sum of the distances from the point $(x, y)$ to the $N$ lines.
• During final testing, the interactive library guarantees that the result returned by this function has an absolute or relative error of no more than $10^{-13}$ compared to the true answer. You can call this function at most $Q_\text{max}$ times.
  • That is, if the result returned by the interactive library is $x$ and the true answer is $y$, then $\frac{|x-y|}{\max(1, y)} \leq 10^{-13}$.

void the_lines_are(std::vector<int> a, std::vector<int> b);

• You must call this function exactly once.
• You must ensure that a and b are arrays of length exactly $N$, where for each $0 \leq i < n$, a[i] and b[i] describe a line.
• You may return these lines in any order.

Examples

The sample interactive libraries grader_1.cpp and grader_2.cpp are provided in the distributed files. These two libraries are identical except for the way they answer queries. You can use these implementations to help you understand and implement the problem. Note that during final testing, the implementation of the interactive library will differ from these sample libraries, so you should not rely on the specific implementation of these graders.

The sample interactive libraries read data from standard input in the following format:

• The first line contains a positive integer representing subtask_id.
• The second line contains three positive integers $N, Q_\text{max}, Q_\text{min}$.
• The following $N$ lines each contain two integers $a_i, b_i$.

After the interaction is complete, the interactive library will output the result returned by your program to standard output. Note that the sample interactive library does not check if your answer is correct; it only outputs the parameters passed when you call the the_lines_are function.

The differences between the two sample interactive libraries are as follows:

• For grader_1.cpp, the library calculates the distance from point $(x, y)$ to all lines when query(x, y) is called.
• For grader_2.cpp, for each query, the library will output query(x, y) = to the standard output stream, and you must input the answer to that query from standard input.

You can use the following commands in your terminal to compile your program:

g++ grader_1.cpp lines.cpp -o lines_1 -O2
g++ grader_2.cpp lines.cpp -o lines_2 -O2

During final evaluation, for any valid interaction process (using no more than $Q_\text{max}$ queries), the interactive library is guaranteed to use no more than $0.2$ seconds and no more than $2\text{ MiB}$ of memory.

Input 1

1
1 10000 10000
1 0

Output 1

the_lines_are({1}, {0})

Note

The following is a valid interaction process for the input above: solve(1, 1) is called. The program calls query(0, 0), which returns $0$. The program calls query(1, 1), which returns $0$. The program calls the_lines_are({1}, {0}).

Subtasks

If you do not return a result within the time limit ($1.0$ seconds) and memory limit ($256\text{ MiB}$) for a test case, or if a runtime error occurs, or if the final returned answer is incorrect, your score for that test case will be $0$.

Otherwise, let $Q$ be the number of times you called the query function in that test case, and $S$ be the full score for that test case:

• If $Q_\text{max} < Q$, your score is $0$.
• If $Q_\text{min} < Q \leq Q_\text{max}$, your score is $S \cdot \left( 1 - 0.7 \cdot \dfrac{Q - Q_\text{min}}{Q_\text{max} - Q_\text{min}} \right)$.
• If $Q \leq Q_\text{min}$, your score is $S$.

In a subtask, your score is the minimum of the scores of all test cases within that subtask.

For all data, $1 \leq N \leq 100$, $-10^4 \leq a_i, b_i \leq 10^4$, $Q_\text{max} = 10^4$, and no two lines are parallel to each other.