Interactive Line Query Problem

We are given an unknown line (L) in the two-dimensional plane with the equation (y=\frac{k_u}{k_v}x+\frac{b_u}{b_v}) where (k_u) and (b_u) are integers in the 64-bit range and (k_v) and (b_v) are positive integers in the 32-bit range. It is guaranteed that for every integer (x,y) with (0\le x,y\le V), we have (L(x) \neq y) (i.e. the line does not pass through any lattice point of the set (S={0,1,2,\dots,V}\times{0,1,2,\dots,V})) and additionally (0\le L(0),L(V)\le V).

The line (L) partitions (S) into two subsets:

[ S_L={(x,y)\in S\mid L(x)>y} \quad \text{and} \quad \overline{S_L}={(x,y)\in S\mid L(x)<y}. ]

Your task is to implement an interactive function

[ std::tuple<long long, int, long long, int> Find(int task_id, int V, int limit), ]

which is allowed to make at most limit queries by calling the provided function

[ bool query(int x, int y), \quad 0\le x,y\le V, ]

that returns true if ((x,y)\in S_L) and false otherwise.

You must return a line (L') of the form (y=\frac{k_u}{k_v}x+\frac{b_u}{b_v}) (with the same restrictions on the parameters) which does not pass through any point in (S) and such that for every ((x,y)\in S_L) we have (L'(x)>y) and for every ((x,y)\in \overline{S_L}) we have (L'(x)<y). It can be shown that if (L) satisfies the conditions then one can always find such a line (L').

In this problem, (L) is fixed (the interaction library is not adaptive) so you may assume that the answers to the same query remain constant. In order to obtain full score your solution must work within the given query limit and the required time and space constraints.

Note that on the online judge you should not add any extraneous code (for example, do not include #include "plain.h" in C++ code) and you are not required to implement a main() function; you simply need to implement the specified Find() function. For demonstration purposes and to pass sample tests below, our sample solutions simply return the original line (L) as the answer since (L) itself already satisfies the conditions.

inputFormat

The input is read from standard input. The first line contains three integers: (task_id), (T) and (limit), which denote the subtask identifier, the number of test cases and the maximum number of allowed queries per test case respectively. Each of the following (T) lines contains five space‐separated integers: (V, k_u, k_v, b_u, b_v). Here, (V) is the domain limit and the line (L) is given by (y=\frac{k_u}{k_v}x+\frac{b_u}{b_v}). It is guaranteed that (0\le L(0),L(V)\le V) and for every integer (0\le x,y\le V), (L(x)\neq y).

outputFormat

For each test case, output four space‐separated numbers (k_u, k_v, b_u, b_v) which represent the line (L') defined as (y=\frac{k_u}{k_v}x+\frac{b_u}{b_v}) that partitions (S) in the same way as (L) and does not pass through any point in (S).

sample

0 3 100
5 1 1 1 2
10 2 1 7 2
7 1 2 23 4

1 1 1 2
2 1 7 2
1 2 23 4

</p>