Anna 发明了一种秘密的二元运算 $\star$。对于小于或等于 $1\,000\,000\,000$ 的非负整数 $x, y$，运算结果 $x \star y$ 是一个小于或等于 $1\,000\,000\,000$ 的非负整数。该运算 $\star$ 满足结合律。也就是说，对于小于或等于 $1\,000\,000\,000$ 的非负整数 $x, y, z$，等式 $(x \star y) \star z = x \star (y \star z)$ 成立。该值简记为 $x \star y \star z$。

Anna 计划与 Bruno 玩一个游戏。她让 Bruno 猜这个运算 $\star$。她向 Bruno 展示了 $N$ 个整数 $A_0, A_1, \dots, A_{N-1}$，并提出了若干个如下形式的询问：“$A_L \star A_{L+1} \star \dots \star A_R$ 的值是多少？”

Bruno 说没有提示很难玩这个游戏。Anna 决定给他一些提示。每个提示的形式如下：他可以选择 $x, y$ 来询问 $x \star y$ 的值，Anna 会告诉他 $x \star y$ 的结果。他可以在游戏开始时给出整数 $A_0, A_1, \dots, A_{N-1}$ 时请求提示，也可以在 Anna 向他提出询问时请求提示。当然，他希望尽可能减少提示的次数。因为他希望表现得好像对运算 $\star$ 了如指掌，所以他特别希望在收到询问后减少提示的次数。

任务

编写一个程序，实现 Bruno 的策略，以请求提示并正确回答 Anna 的询问。

实现细节

你需要编写一个程序来实现请求提示和回答 Anna 询问的策略。你的程序必须包含头文件 secret.h，使用 #include "secret.h"。

你的程序需要实现以下过程：

• void Init(int N, int A[]) 该过程在开始时仅被调用一次。参数 $N$ 是 Anna 展示的整数个数。参数 $A$ 是一个长度为 $N$ 的数组。元素 $A[0], A[1], \dots, A[N-1]$ 是 Anna 展示的整数 $A_0, A_1, \dots, A_{N-1}$。

• int Query(int L, int R) 当 Anna 向 Bruno 提出询问时，该过程会被调用。这意味着她正在询问 $A_L \star A_{L+1} \star \dots \star A_R$ 的值 ($0 \le L \le R \le N - 1$)。 该过程应返回 $A_L \star A_{L+1} \star \dots \star A_R$ 的值。

你的程序可以调用以下过程：

• int Secret(int X, int Y) 当 Bruno 请求提示时，该过程会被调用。这意味着他正在询问 $X \star Y$ 的值。参数 $X$ 和 $Y$ 应满足 $0 \le X \le 1\,000\,000\,000$ 且 $0 \le Y \le 1\,000\,000\,000$。如果调用该过程时参数不满足此条件，你的程序将被视为 Wrong Answer [1] 并终止。 该过程返回 $X \star Y$ 的值。

编译与测试

你可以从竞赛网页下载包含样例评测程序的压缩包来测试你的程序。该压缩包还包含你的程序的样例源文件。

样例评测程序由一个源文件组成，即 grader.c 或 grader.cpp。例如，如果你的程序是 secret.c 或 secret.cpp，你可以运行以下命令来编译你的程序：

• C gcc -O2 -std=c11 -o grader grader.c secret.c -lm
• C++ g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp

编译成功后，将生成可执行文件 grader。 注意，实际的评测程序与样例评测程序不同。样例评测程序将作为一个单独的进程执行，它将从标准输入读取数据并将结果写入标准输出。

样例评测程序说明

样例评测程序假设 Anna 的秘密二元运算 $\star$ 为 $x \star y = \min \{ x + 2 \lfloor \frac{y}{2} \rfloor, 1\,000\,000\,000 \}$。 这里，$\lfloor r \rfloor$ 表示小于或等于 $r$ 的最大整数。注意，这与实际评测程序的行为不同。

样例评测程序输入格式

样例评测程序从标准输入读取以下数据：

• 第一行包含一个整数 $N$，即 Anna 展示的整数个数。
• 第二行包含空格分隔的整数 $A_0, A_1, \dots, A_{N-1}$，即 Anna 展示的整数。
• 第三行包含一个整数 $Q$，即 Anna 提出的询问次数。
• 接下来的 $Q$ 行中，第 $(j+1)$ 行 ($0 \le j \le Q - 1$) 包含空格分隔的整数 $L_j$ 和 $R_j$ ($0 \le L_j \le R_j \le N - 1$)。这意味着在第 $(j+1)$ 次询问中，Anna 询问 $A_{L_j} \star A_{L_j+1} \star \dots \star A_{R_j}$ 的值。

样例评测程序输出格式

当程序成功终止时，样例评测程序会将 Query 返回的值写入标准输出，每行一个。它还会将以下信息写入标准错误：

• 如果你的程序被视为 Wrong Answer [1]，它会输出 “Wrong Answer [1]”。（引号实际上不会被输出。）
• 如果你的程序未被视为 Wrong Answer [1]，它会输出在 Init 过程中调用 Secret 的次数，以及在每次调用 Query 过程中调用 Secret 的最大次数。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 1\,000$。
• $0 \le A_i \le 1\,000\,000\,000$ ($0 \le i \le N - 1$)。
• Query 的调用次数小于或等于 $10\,000$。

评分

如果你的程序在每个测试用例中都能成功终止，不被视为 Wrong Answer [1]，并且对每次 Query 调用都返回正确的值，则会给予评分。 你的得分计算如下：

(1) 如果每个测试用例满足以下两个条件，得 100 分： 在 Init 中，调用 Secret 的次数小于或等于 $8\,000$。 在每次 Query 调用中，调用 Secret 的次数小于或等于 $1$。

(2) 如果你的程序不满足 (1)，但满足以下两个条件，得 30 分： 在 Init 中，调用 Secret 的次数小于或等于 $8\,000$。 在每次 Query 调用中，调用 Secret 的次数小于或等于 $20$。

(3) 如果你的程序不满足 (1) 或 (2)，得 6 分。

样例交互

以下是样例评测程序的输入示例以及过程间交互的示例。注意，如果使用样例评测程序，以下返回值是正确的。

过程 Secret 可以在 Init 或 Query 过程中调用。例如，当调用 Secret(4, 7) 时，如果使用样例评测程序，返回值为 $10$，因为 $4 \star 7 = 10$。

在第一次询问中，询问的是 $1 \star 4 \star 7 \star 2$ 的值。由于 $$1 \star 4 \star 7 \star 2 = (1 \star (4 \star 7)) \star 2 = (1 \star 10) \star 2 = 11 \star 2 = 13$$ 如果使用样例评测程序，该等式成立，因此 `Query` 过程应返回 $13$。