Roxette 是一位老派的技术极客，她偶然发现了一个包含 $N$ 个不同整数的数组 $v_0, v_1, v_2, \dots, v_{N-1}$。她对这个数组非常感兴趣，并想将其保存在软盘上。然而，由于软盘剩余空间不足，Roxette 不得不退而求其次：她无法保存整个数组，而是计划保存一个位数组，以便能够回答以下形式的查询：

$query(a, b) = id$，其中 $a \le id \le b$ 且 $v_{id} = \max(v_a, v_{a+1}, \dots, v_{b-1}, v_b)$

换句话说，该查询返回给定子数组中最大值的下标。

Roxette 现在需要你的帮助。你需要进行两次交互！首先，她会提供给你这个有趣的数组，你必须告诉她要在软盘上保存什么样的位序列。其次，如果她需要知道某些查询的答案，她会提供给你你之前告诉她要保存的位序列以及她需要回答的查询，而你必须为每个查询提供正确的答案。

交互

这是一个双重交互任务！ 选手必须实现两个函数。第一个函数如下：

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

该函数将在第一次交互中被调用且仅被调用一次，并向选手提供 Roxette 感兴趣的数组。在实现此函数时，选手必须调用以下函数且仅调用一次，该函数由评测程序实现：

(C) void save_to_floppy(int L, char* bits);
(C++) void save_to_floppy(const std::string& bits);

该函数告诉 Roxette 在她的软盘上保存什么位序列。参数 $L$ 表示要保存的位数。参数 bits 必须是一个字符序列（只允许字符 '0' 和 '1'）。

选手必须实现的第二个函数是：

(C) int* solve_queries(int subtask_id,
                       int N, int L, char* bits,
                       int M, int* a, int* b);
(C++) std::vector<int> solve_queries(int subtask_id,
                                     int N, const std::string& bits,
                                     const std::vector<int>& a,
                                     const std::vector<int>& b);

该函数将在第二次交互中被调用且仅被调用一次，并向选手提供 Roxette 感兴趣的数组长度、选手之前指示 Roxette 保存到软盘上的位数组以及 $M$ 个查询。

第 $i$ 个查询的参数为 $a[i]$ 和 $b[i]$。

该函数必须返回一个包含 $M$ 个整数的数组，表示每个查询的答案（第 $i$ 个整数必须是第 $i$ 个查询的答案）。

重要提示：选手的程序将运行两次，每次交互运行一次。因此，选手程序在第一次运行中计算出的任何数据在第二次运行中都将无法访问。

数据范围

• $-10^9 \le v_i \le 10^9$，对于所有 $0 \le i \le N - 1$
• $1 \le L \le 200\,000$

子任务

子任务 1（7 分）

• $1 \le N \le 500$
• $0 \le v_i < N$，对于所有 $0 \le i \le N - 1$
• $1 \le M \le 1\,000$
• 如果所有测试点均正确解决，则该子任务得 7 分，否则得 0 分。

子任务 2（21 分）

• $1 \le N \le 10\,000$
• $1 \le M \le 20\,000$
• 每个测试点的得分为 $\min(1, \frac{1}{2^{\frac{L}{N} - 1 - \log_2 N}})$。子任务得分为每个测试点得分的最小值乘以 21。

子任务 3（72 分）

• $1 \le N \le 40\,000$
• $1 \le M \le 80\,000$
• 每个测试点的得分为 $\min(1, \frac{1}{2^{\frac{L}{N} - 2}})$。子任务得分为每个测试点得分的最小值乘以 72。

样例

在第一次交互中，选手的函数将被调用：

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

该函数随后可以选择在软盘上保存以下位：

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

第一次运行的选手程序现在将被终止，因此该程序存储在内存中的任何数据都将丢失。

在第二次交互中，选手的函数将被调用：

solve_queries(
/* subtask_id = */ 3,
/* 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}