This is an interactive problem.

In a 2D plane, there is an unknown line $L$ that is not parallel to the $y$-axis. Let $L(x_0)$ denote the $y$-coordinate of the intersection of line $L$ and the line $x = x_0$.

Given a range $V$, $L$ additionally satisfies the following properties: For any integers $0 \le x, y \le V$, $L(x) \neq y$; $0 \le L(0), L(V) \le V$.

At this point, $L$ divides the set $S = \{0, 1, 2, \dots, V\} \times \{0, 1, 2, \dots, V\}$ into two point sets $S_L = \{(x, y) \in S \mid L(x) > y\}$ and $\overline{S_L} = \{(x, y) \in S \mid L(x) < y\}$, and both are non-empty.

You can make at most limit queries to the interactor. Each query provides integers $0 \le x, y \le V$, and you will receive whether $(x, y)$ belongs to $S_L$ or $\overline{S_L}$.

You need to find a line $L'$ that does not pass through any point in $S$, and $L'$ divides $S$ into the same two point sets as $L$. Formally, $L'$ must satisfy $\forall(x, y) \in S_L, L'(x) > y$ and $\forall(x, y) \in \overline{S_L}, L'(x) < y$.

Implementation Details

Ensure your program starts with #include "plain.h".

You do not need to, and should not, implement the main function. You need to implement the following function:

• std::tuple<long long, int, long long, int> Find(int task_id, int V, int limit);

  • task_id represents the subtask ID, V represents the range, and limit represents the maximum number of queries.
  • You need to return a tuple $(k_u, k_v, b_u, b_v)$ representing the line $L'$ given by the equation $y = \frac{k_u}{k_v} x + \frac{b_u}{b_v}$.
  • You must ensure $k_u$ and $b_u$ are within the long long range, $k_v$ and $b_v$ are within the int range, and $k_v, b_v > 0$. You do not need to ensure the fractions are in simplest form. It can be proven that under the constraints of this problem, such a $(k_u, k_v, b_u, b_v)$ always exists.
  • In the final tests, the interactor will call the Find function $T \le 10^4$ times.

You can use std::make_tuple(a, b, c, d) to pack $a, b, c, d$ into a tuple.

You can call the following function to perform a query:

• bool query(int x, int y);

  • You must ensure $0 \le x, y \le V$, and the number of calls to this function within a single test case does not exceed limit.
  • When $(x, y) \in S_L$, the function returns true, otherwise it returns false.

The interactor is not adaptive, meaning $L$ is fixed and does not change during the interaction process.

Examples

Input 1

1 0 3 20
2 4 5 11 11 6
3 4 -11 15 17 5
4 4 2 15 4 5

Output 1

Correct.
8

Note

task_id = 0 indicates that this set of data is an example.

Figure 1: Function graph corresponding to the first data set

Figure 2: Function graph corresponding to the second data set

Figure 3: Function graph corresponding to the third data set

Subtasks

For all test data, $2 \le V \le 10^9$, $1 \le T \le 10^4$, $100 \le \text{limit} \le 3,666$.

Special Property A: It is guaranteed that the line $L$ is obtained by shifting $y = \frac{a}{b}x$ upwards by at most $\frac{1}{2b}$, where $0 < b \le V$.