题目描述

Tom 把 $n$ 个正整数写成一排，记作 $a_1, a_2, \dots, a_n$，每一个都不超过 $10^6$。33DAI 看不到这些数，只能向 Tom 询问某一段的和：

• 给出 $l, r$，问「$a_l + a_{l+1} + \dots + a_r$ 是多少」。

33DAI 想知道的只有一件事：这 $n$ 个数里最大值与最小值的差（也就是极差）。请你帮他问出来，并且问的次数要尽量少。

本题是函数式交互题。你不需要写 main 函数，只要实现下面两个函数（声明在随题下发的 recover.h 里）：

void init(int t, int n);
long long recover();

• init(t, n)：每个测试点开始时调用一次。$t$ 是这个测试点里数组的组数，$n$ 是每组的长度（各组相同）。
• recover()：求出当前这一组数组的极差并返回。每组开始时询问次数清零。

你可以调用下面这个函数向评测程序提问：

long long query(int l, int r);

• 返回 $a_l + a_{l+1} + \dots + a_r$，要求 $1 \le l \le r \le n$。
• 若下标不合法，本测试点判为 Wrong Answer。

评分方式：记 $M$ 为"这个测试点里，某一组问得最多的次数"。

• 只要有任何一组答错，本测试点得 $0$ 分；
• $M > 3000$ 直接判 Wrong Answer；
• 要确定 $n$ 个数至少需要 $n$ 次询问，所以下界是 $n$。$M \le n$ 得满分； $n < M \le 2n$ 时分数从满分线性降到一半；$2n < M < 8n$ 时从一半线性降到 $0$；$M \ge 8n$ 得 $0$ 分。

输入格式

本题没有传统意义上的输入文件：数据由评测程序（grader）读入，你只要实现上面两个函数。

随题下发的文件（见「附加文件」）：

• recover.h：接口声明；
• grader.cpp：示例评测程序，只用来在本地把你的程序跑起来；
• compile.sh：编译脚本。

本地编译命令（把你自己的代码保存为 foo.cc，与上面三个文件放在同一个目录）：

g++ -o foo foo.cc grader.cpp -O2 -std=c++14

示例 grader 的本地输入格式是：第一行两个整数 $t, n$；之后 $t$ 行每行 $n$ 个整数， 就是这一组的隐藏数组。它会打印每一组用了多少次询问。

注意：示例 grader 只用于本地自测，它的数据格式、数据范围与判分方式都和正式评测不同； 正式评测使用另一份 grader，请以题面写明的接口与规则为准。

输出格式

不需要输出任何东西：recover() 的返回值就是答案，由评测程序收集。

样例

某个测试点里 $t = 2$、$n = 3$，两组隐藏数组分别是 $[5, 3, 8]$ 与 $[7, 7, 7]$。

第一组：

你的程序                评测程序
query(1, 2)   ->        8        （a1 + a2 = 8）
query(1, 3)   ->        16       （a1 + a2 + a3 = 16）
query(2, 3)   ->        11       （a2 + a3 = 11）
recover() 返回 5                 （最大值 8、最小值 3，极差 5）

第二组三个数都是 $7$，极差是 $0$，所以 recover() 返回 $0$。

这个测试点里最多的一组问了 $3$ 次、下界也是 $3$，所以 $M = n = 3$，得满分。

提示

• 本题是函数式交互题：recover.h、grader.cpp、compile.sh 会随题目一起下发，你只提交实现 init / recover 的源文件。
• 每个测试点里有好几组数据，同一组内的询问次数单独统计，最后取最大的那个。
• 一共至少要 $n$ 次询问才能定出 $n$ 个数，请想想怎样用恰好 $n$ 次询问把数组恢复出来。
• 注意 $n$ 很小时（比如 $n = 1$、$n = 2$）的边界。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 200$；
• $1 \le n \le 1000$；
• $1 \le a_i \le 10^6$。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点计分（子任务 type: sum）。