这是一道通信题。

给定正整数 $N$，pA 有 $N$ 个两两不同的整数 $v_0,\cdots,v_{N-1}$，pB 有 $M$ 个区间 $[a_0,b_0],\cdots,[a_{M-1},b_{M-1}]$。

对每个 $i\in[0,M)$，pB 想知道 $v_{a_i},v_{a_i+1},\cdots,v_{b_i}$ 中最大元素的下标是多少，为此 pA 可以向 pB 发送至多 $2\cdot 10^5$ 个 bit 的信息。

• 注意，pA 向 pB 发送的信息数量上界仅为评测时使用的一个硬性上界，为了取得满分，pA 实际向 pB 发送的信息必须符合各个子任务的评分规则。

编写一个程序，实现 pA 与 pB 两个人之间的策略。

实现细节

你不需要，也不应该实现 main() 函数，或在任何文件以及标准输入/输出流中读入或输出任何信息。

本题仅支持 C++ 语言，你需要实现两份代码，来分别实现 pA 与 pB 的策略。

第一份代码为 save.cpp，它需要包含头文件 save.h，并通过实现以下函数来描述 pA 的策略：

void read_array(int subtask_id, const std::vector <int> &v);

• 在每组测试数据中，该函数会被调用恰好一次；
• 参数中的 subtask_id 表示当前测试点的子任务编号；
• 参数中的 v 表示给定的序列 $v_0,\cdots,v_{N-1}$。

你可以调用以下函数：

void save_to_floppy(const std::string &bits);

• 你只能在 read_array 函数中调用该函数，且调用恰好一次；
• 参数中的 bits 是 $\texttt{01}$ 字符串，表示 pA 向 pB 发送的信息。

第二份代码为 load.cpp，它需要包含头文件 load.h，并通过实现以下函数来描述 pB 的策略：

std::vector <int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector <int> &a, const std::vector <int> &b);

• 在每组测试数据中，该函数会被调用恰好一次；
• 参数中的 subtask_id 表示当前测试点的子任务编号；
• 参数中的 bits 是 $\texttt{01}$ 字符串，表示 pA 向 pB 发送的信息；
• 参数中的 a 和 b 描述 $M$ 组询问，第 $i$ 组询问的 $a_i$ 和 $b_i$ 分别为 a[i] 和 b[i]。

样例交互库

在下发文件中，你可以找到样例交互库 grader.cpp，你可以通过样例交互库的实现来帮助你理解并实现这道题目。需要注意的是，在进行最终测试时，交互库的实现与样例交互库有所不同，因此你不应当依赖此交互库的实现。

样例交互库将从标准输入中按照以下格式读入数据：

• 第一行，一个整数，表示 subtask_id；
• 第二行，两个正整数 $N,M$；
• 第三行，$N$ 个整数 $v_0,\cdots,v_{N-1}$；
• 之后 $M$ 行，每行三个非负整数，分别表示 $a_i,b_i$ 以及这组询问的正确答案。

当程序成功结束后，样例交互库将输出以下信息到标准输出：

• 如果你的答案正确，它将输出 OK!；
• 如果你的答案错误，它将输出对应的错误信息。

你可以在终端使用以下命令来编译你的程序：

g++ grader.cpp save.cpp load.cpp -o prog -O2

需要注意的是，上述命令会将 grader 与你实现的两个程序一起编译，你需要避免不同代码之间的全局变量或函数重名。

请不要在两份代码中共享全局变量。在最终评测时，save 过程与 load 过程将在两个不同的进程中被调用，它们之间不能共享任何全局变量与函数。

样例

以下是一组可能的对样例交互库的输入：

2
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3

以下是一次合法的交互过程：在程序 save 中，交互库进行以下调用：

read_array(
  /* subtask_id = */ 2,
  /* v          = */ {40, 20, 30, 10});

选手程序在该函数中进行以下调用：

save_to_floppy(
  /* bits = */ "001100");

随后，在程序 load 中交互库进行以下调用：

solve_queries(
  /* subtask_id = */ 2,
  /* N          = */ 4,
  /* bits       = */ "001100",
  /* a          = */ {0, 0, 0, 0, 1, 1, 1, 2, 2, 3},
  /* b          = */ {0, 1, 2, 3, 1, 2, 3, 2, 3, 3});

该函数需要返回如下 $M$ 个整数的数组：

{0, 0, 0, 0, 1, 2, 2, 2, 2, 3}

在最终评测时，对于任何合法的交互过程，保证交互库使用的时间不超过 $0.2$ 秒，使用的内存不超过 $4\text{ MiB}$。

子任务

如果你在某个测试点中没有在时间限制（$1.0$ 秒）与空间限制（$512\text{ MiB}$）内返回结果，或发生了运行时错误，或最终返回的答案不正确，则你在该测试点的得分为 $0$。

否则，设 $L$ 为 pA 向 pB 发送的信息长度，每个子任务中的测试点会有不同的评分方式。

在一个子任务中，你所得到的分数即为所有测试点分数的最小值。

对于所有数据，$N\le 4\cdot 10^4$，$M\le 8\cdot 10^4$，$-10^9\le v_i\le 10^9$，$v_i$ 两两不同。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$