Interactive Line Recovery

This is a functional interactive problem. In a two-dimensional Cartesian coordinate system, there are (N) lines given by (f_i(x) = a_i x + b_i) where (a_i) and (b_i) are integers satisfying (|a_i|,|b_i| \le 10^4). It is guaranteed that no two lines are parallel. You may choose any real point (P = (x, y)) (with (|x|,|y| \le 10^{12})) and query the interactive judge using the function

[ query(x, y): \text{ returns } \sum_{i=1}^{N} d(P, L_i) \quad \text{(Euclidean distance)} ]

Your task is to determine the exact equations of all (N) lines by strategically using queries. There are limits on the maximum number of queries allowed:

• For full score, the number of queries must be no greater than (q).
• For non-zero score, the number of queries must be no greater than (Q).

You are required to implement the following function without writing a main function:

void solve(int subtask_id, int N);

You can call the following functions provided by the interactive library:

// Use to query a point (x, y) with |x|,|y| \le 10^{12}
long double query(long double x, long double y);

// Call exactly once to report your answer. The vectors a and b represent the slopes and intercepts of the N lines respectively.
void the_lines_are(std::vector<int> a, std::vector<int> b);

Note: This is an interactive problem. The input you receive is managed by the interactor. For testing and hacking purposes, the judge might supply the hidden lines after the initial parameters.

inputFormat

The interactive judge first provides two integers: (subtask_id) and (N). The hidden lines' parameters ((a_i) and (b_i)) satisfy (|a_i|, |b_i| \le 10^4) and no two lines are parallel. Although normally these are hidden, for hacking purposes the judge may provide (N) subsequent lines containing the integers (a_i) and (b_i).

outputFormat

Your solution must ultimately call the provided function (the_lines_are) exactly once to output your discovered slopes and intercepts of the (N) lines. In a hacking environment, the expected output is the correct list of slopes and intercepts in the same order as the hidden test data.

sample

1
2
1 1
-1 2

1  -1
1  2