这是一道交互题。

题目描述

给定一个数组 $a$，数组 $a$ 中的元素都为正整数，下标从 $0$ 开始编号，它们互不相同，且小于等于 $10^9$。

你可以执行两种操作来确定数列 $a$ 中的元素：

1. 你可以给定一个位置 $i$，交互器会返回 $a_i$ 的值，这个操作只能执行 $M_1$ 次。
2. 你可以给定一个集合 $S$，交互器会以任意顺序返回集合 $S$ 内元素两两之差的绝对值，这个操作只能执行 $M_2$ 次。

你需要通过以上两种操作确定数列 $a$ 中的所有元素。

实现细节

你不需要，也不应该实现主函数，你只需要实现函数 find(n, M1, M2)，这里的 $n$ 表示的是数列 $a$ 的长度，$M_1$ 和 $M_2$ 分别表示两类查询的次数限制。

你可以通过调用如下三个函数来和交互库进行交互：

1. qry1(pos)，这个函数会返回 $a_{pos}$ 的值。
2. qry2(S)，其中 $S$ 表示一个集合，设你查询的集合大小为 $k$，查询的集合内的元素依次为 $s_0, s_1,\ldots,s_{k−1}$，其会返回 $\frac{k\times (k-1)}{2}$ 个值，他们表示所有 $|a_{s_c}-a_{s_d}|(0\le c<d<k)$，即你询问的下标对应的数的两两之差的绝对值。
3. answer(A)，当你知道了数列 $A$ 时，你可以调用此函数来返回你已知的答案，一旦调用了本函数，运行完本函数后，程序将自动结束。

交互说明

1. 请确保你的程序开头有 #include "difference.h"。
2. 你需要实现的函数 find 的接口信息如下：void find(int n, int M1, int M2)
3. 你可以调用的交互函数的接口如下：
   • int qry1(int pos)：
     • 特别的，参数 $pos$ 应满足是 $0$ 到 $n − 1$ 之间的一个整数，如果不满足，你的程序将得到不可知的后果。
   • vector<int> qry2(const vector<int> &S)：
     • 你需要传入一个 vector<int> 参数的类型 $S$ 表示你需要查询的集合 $S$，函数 qry2(S) 将返回一个 vector<int> 类型，设 $S$ 的大小为 $k$，其返回值将包含 $\frac{k\times (k-1)}{2}$ 个元素，编号依次为 $0\sim \frac{k\times (k-1)}{2}-1$。特别的，$S$ 之中的参数 $s_i$ 应为 $0$ 到 $n − 1$ 之间的一个整数，且 $s_i, s_j$ 应该两两不同。
   • void answer(const vector<int> &ret)：
     • 其中 $ret$ 存储你已知道的答案，$ret$ 的大小应为 $n$，并且 $ret$ 中的元素应按照数组下标顺序排列，从 $0$ 开始编号至 $n − 1$。
     • 一旦调用了本函数，运行完本函数后，程序将自动结束。
4. • 本题保证所使用的数列 $a$ 在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。
   • 数据保证在调用次数限制下，交互库运行所需的时间不超过 $0.5s$，交互库使用的内存大小固定，且不超过 $128MB$。
5. 你需要在文件所在目录下使用 g++ grader.cpp difference.cpp -o difference -O2 -std=c++11 命令进行编译。
6. • 对于编译得到的可执行程序：
   • 可执行文件将从标准输入读入以下格式的数据：
   • 第一行三个整数 $n, M_1, M_2$，表示数组长度，操作 $1$ 和操作 $2$ 的限制次数。
   • 第二行 n 个正整数，其中第 i 个正整数表示 ai。
7. • 任何试图攻击交互库的行为将视为作弊，给予 $0$ 分处理。
   • difference.cpp 中只需实现函数功能，不需要进行文件操作。

交互示例

假设可执行文件读入的数据为：

4 2 26
1 2 3 4

数据的第一行三个整数分别表示 $n, M_1, M_2$，分别表示 $a$ 数组的长度，和两类查询的次数限制。

下面是一个正确的交互过程：

注意我们保证了 $a_i$ 互不相同。

评分方式

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点中，你得到满分，当且仅当：

1. 你调用的 qry1, qry2 操作的次数分别不超过 $M_1, M_2$。
2. 你调用了恰好一次函数 answer，且结果正确。

数据规模与约定

本题共 $20$ 个测试点，每个测试点的数据规模见下表。对于全部测试点，保证 $n \le 250, M_1 \ge 2, M_2 \ge 30$，且 $a_i$ 互不相同。