题目背景

这是一个提交函数题。

你无法直接获得所有直线的参数，只能通过调用评测器提供的函数进行询问，并最终报告所有隐藏直线。

题目描述

给定 N 条隐藏直线，第 i 条直线的表达式为：

$$f_i(x)=a_i x+b_i$$

其中所有 a_i 两两不同，并且每条直线都满足：在整数区间 [-10^9,10^9] 内，至少存在 3 个整数点，使得该直线在这些点上的函数值等于所有隐藏直线中的最大值。

更形式化地说，对于每一条隐藏直线 f_i，至少存在 3 个互不相同的整数 x，满足：

$$f_i(x)=\max_{1\le j\le N} f_j(x)$$

你需要通过尽量少的询问，找出所有隐藏直线。

实现要求

你需要实现如下函数：

void solve(int n);

评测器会提供以下函数：

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

其中：

• query(x)：返回所有隐藏直线在整数点 x 处的最大值；
• answer(a,b)：报告一条直线 y=ax+b。

你必须 恰好 调用 answer 共 n 次，顺序任意。

提交要求

你的提交程序必须满足以下要求：

• 必须包含头文件：

#include "gcd5.h"

• 不能包含 main 函数；
• 不能读写标准输入输出；
• 只需实现 solve(int n) 函数。

输入格式

本题为提交函数题。

你的程序不通过标准输入读取数据，所有信息均通过评测器传入。

评测器会调用：

solve(int n)

其中 n 表示隐藏直线的条数。

输出格式

本题为提交函数题。

你的程序不通过标准输出输出答案，而是通过调用：

answer(a, b)

来报告一条直线 y=ax+b。

你需要恰好报告全部 n 条隐藏直线，每条恰好报告一次，顺序任意。

交互 / 评测说明

你可以在 solve(int n) 中多次调用：

long long query(int x)

来查询整数点 x 处所有隐藏直线函数值的最大值。

即返回值为：

$$\max_{1\le i\le N} (a_i x+b_i)$$

注意：

• query 的参数 x 必须是整数；
• x 必须满足 -10^9 <= x <= 10^9；
• 非法调用会导致该测试点得分为 0。

数据范围

• 1 <= N <= 100000
• |a_i| <= 10^9
• |b_i| <= 10^18
• query 的参数 x 必须满足 -10^9 <= x <= 10^9

评分规则

若出现以下任一情况，则该测试点得分为 0：

• 进行了非法询问；
• 没有正确找出所有隐藏直线；
• 询问次数超过 5 \times 10^6。

否则，设总询问次数为 Q，则该测试点的得分比例为：

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

每个子任务的得分为该子任务内所有测试点得分比例的最小值，再乘以该子任务分值。

子任务

子任务	分值	N \le
1	18	100
2	33	5000
3	49	100000

提示

1. 所有隐藏直线的斜率互不相同。
2. 你只能观察到若干个整数点处的上凸包函数值。
3. 每条直线都保证在整数区间 [-10^9,10^9] 内至少有 3 个整数点成为最大值，这一条件对恢复全部直线十分关键。
4. 由于本题按询问次数计分，因此除了正确性之外，还需要关注算法的查询复杂度。