Niki 构思了 $N$ 条隐藏的直线（或线性函数），你需要找出它们。更正式地说，每条直线 $i$ 由一对系数 $(a_i, b_i)$ 定义，并定义了线性函数 $f_i(x) = a_i \cdot x + b_i$。

Niki 不喜欢分数，因此所有系数均为整数。

为了找到这些隐藏的直线，你可以询问在某个你指定的 $x$ 值下，所有直线中的最大值。正如你所了解的，Niki 不喜欢分数，因此你只能针对整数 $x$ 进行询问。正式地，该问题的回答是：$\max_{1 \le i \le N} f_i(x)$。

该问题保证是有解的。除了上述条件外，还保证每条直线在至少 3 个整数 $x \in [-10^9; 10^9]$ 上是最大的，换句话说，对于每条直线 $i$，存在至少 3 个 $x \in [-10^9; 10^9]$ 使得对于所有 $j \neq i$，都有 $f_i(x) \ge f_j(x)$。此外，不存在两条斜率 $a_i$ 相同的直线。

请编写一个程序，使用尽可能少的询问次数，找出这些隐藏的直线！

输入格式

无。

数据范围

• $1 \le N \le 10^5$
• $|a_i| \le 10^9$，且每个 $a_i$ 均为整数。
• $|b_i| \le 10^{18}$，且每个 $b_i$ 均为整数。

交互

本题为交互题，你只需要编写一个函数 solve，其类型如下：

void solve(int n);

该函数将被调用恰好一次，参数为直线的数量。你的实现可以使用以下 2 个函数：

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

使用 query(x) 函数，你可以获取在对应 $x$ 下所有直线中的最大值。你在某个测试点中获得的得分取决于询问次数。你只能在 $x \in [-10^9; 10^9]$ 的范围内使用此函数。

answer 函数必须被调用恰好 $n$ 次，每次对应一条找到的直线。调用顺序无关紧要。

你的代码中不应包含 main 函数，但可以包含任何其他辅助函数、类、变量等。你的代码必须包含头文件 gcd5.h。

实现细节

对于本地测试，我们提供了本地评测器 Lgrader.cpp 和 gcd5.h 文件的副本。你需要将你的代码与本地评测器一起编译以进行测试。你可以将它们放在同一个文件夹中并使用以下命令：

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

子任务

给定子任务的得分等于该子任务中所有测试点的最低得分。

说明

对于每个测试点，你将获得一个根据以下方式计算的得分：

1. 如果你进行了无效的询问，或者未能正确猜出隐藏的直线，你将获得 0 分。
2. 设 $Q$ 为你进行的询问总次数。
3. 如果 $Q > 5 \cdot 10^6$，你将获得 0 分。
4. 否则，该测试点的得分为： $$\min \left\{ 0.25 + 0.75 \times \left( \frac{4N}{Q} \right)^2, 1.0 \right\}$$

样例

设 $N = 2$，隐藏的直线为 $(1, -5)$ 和 $(-1, 5)$。一个可能的交互过程如下：

输入 1

solve(2)

输出 1

query(1)

说明 1

4

输入 2

query(5)

输出 2

0

输入 3

query(6)

输出 3

1

输入 4

answer(-1, 5)

输入 5

answer(1, -5)