说明

题目与 GCD 毫无关系 :)

妮基已经想好了 $N$ 条隐藏的直线（或线性函数），而你需要找出它们。形式化地，第 $i$ 条直线由一对系数 $(a_i, b_i)$ 定义，并表示线性函数 $f_i(x) = a_i \cdot x + b_i$。

妮基不喜欢分数，因此所有系数都是整数。

为了找到这些隐藏的直线，你可以提出关于“在给定整数 $x$ 处，哪条直线取得最大值”的查询。正如你已了解到的，妮基讨厌小数，所以你只能对整数值 $x$ 提出这个问题。形式上，对该问题的回答是：$\max_{1 \le i \le N} f_i(x)$。

题目保证有解。除了上述条件外，还保证每条直线在区间 $[-10^9; 10^9]$ 内至少有 $3$ 个整数值 $x$ 使其成为最大值；换句话说，对于每条直线 $i$，存在至少 3 个值 $x \in [-10^9; 10^9]$，使得对所有 $j \ne i$，都有 $f_i(x) \ge f_j(x)$。此外，没有两条直线具有相同的斜率 $a_i$。

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

交互格式

本题为交互式题目，你只需实现一个类型为以下的 solve 函数：

void solve(int n);

该函数将被精确调用一次，参数等于直线的数量。你的实现可以使用以下两个辅助函数：

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。

#include "gcd5.h"

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

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

提示

示例

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

选手	评测机
	solve(2)
query(1)	4
query(5)	0
query(6)	1
answer(-1, 5)
answer(1, -5)

子任务

子任务	分数	$N \le$
$1$	$18$	$100$
$2$	$33$	$5000$
$3$	$49$	$10^5$

某子任务的得分等于其所有子测试点中得分的最小值。

评分方式

对于每个测试点，你将获得一个按以下方式计算的结果：

1. 如果你提出无效查询，或未能正确识别所有隐藏的直线，则得分为 0。
2. 设 $Q$ 为你提出的总查询次数。
3. 如果 $Q > 5 \times 10^6$，则得分为 0。
4. 否则，该测试点的得分为：

$$\min\left\{ 0.25 + 0.75 \times \left( \frac{4N}{Q} \right)^2,\ 1.0 \right\}$$

限制条件

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