JOI-kun 正在策划一场抽奖活动。本次抽奖活动将使用偶数个袋子。每个袋子最初包含一些红球和蓝球（可能为零）。参与者将不断来到抽奖现场，直到至少有一个袋子变空为止。每位参与者从每个袋子中各抽取一个球。如果他们抽到的红球总数和蓝球总数相等，他们将获得一个奖品。抽出的球不会放回袋子中。
作为准备工作，JOI-kun 准备了 $N$ 个袋子，编号为 $0$ 到 $N - 1$。袋子 $i$ ($0 \le i \le N - 1$) 包含 $X_i$ 个红球和 $Y_i$ 个蓝球。
在抽奖活动中，将选择部分袋子使用。共有 $Q$ 个选择袋子的方案。在第 $j$ 个方案（$1 \le j \le Q$）中，使用袋子 $L_j, L_j + 1, \dots, R_j$。这里，$R_j - L_j + 1$ 为偶数。
为了准备活动的奖品，JOI-kun 想要知道，对于每个方案，参与者能够获得的最大奖品总数是多少。请编写一个程序，给定袋子的内容和方案，返回每个方案中参与者能够获得的最大奖品总数。
实现细节
你需要提交一个文件。
该文件为 lottery.cpp。程序应使用预处理指令 #include 包含 lottery.h。
在 lottery.cpp 中，应实现以下函数。
void init(int N, int Q, std::vector<int> X, std::vector<int> Y)- 此函数在开始时仅调用一次。
- 参数 $N$ 是 JOI-kun 准备的袋子数量 $N$。
- 参数 $Q$ 是选择袋子的方案数量 $Q$。
- 参数 $X$ 是一个长度为 $N$ 的数组。$X[i]$ ($0 \le i \le N - 1$) 是袋子 $i$ 中红球的数量。
- 参数 $Y$ 是一个长度为 $N$ 的数组。$Y[i]$ ($0 \le i \le N - 1$) 是袋子 $i$ 中蓝球的数量。
int max_prize(int L, int R)- 此函数在
init函数调用后会被调用 $Q$ 次。 - 在第 $j$ 次调用（$1 \le j \le Q$）此函数时：
- 参数 $L$ 是第 $j$ 个方案的 $L_j$ 值。
- 参数 $R$ 是第 $j$ 个方案的 $R_j$ 值。
- 此函数必须返回在第 $j$ 个方案中参与者能够获得的最大奖品总数。
- 此函数在
重要说明
- 你的程序可以实现其他内部使用的函数，或使用全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
编译与测试
你可以从竞赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你的程序的示例源文件。
示例评测程序文件为 grader.cpp。要测试你的程序，请将 grader.cpp、lottery.cpp 和 lottery.h 放在同一目录下，并使用以下命令进行编译：
g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp
或者，你可以通过运行压缩包中包含的 compile.sh 文件来执行：
./compile.sh
如果编译成功，将生成一个名为 grader 的可执行文件。
注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它将从标准输入读取输入数据并将结果写入标准输出。
输入格式
示例评测程序从标准输入读取以下格式的输入：
$N \ Q$ $X_0 \ X_1 \ \dots \ X_{N-1}$ $Y_0 \ Y_1 \ \dots \ Y_{N-1}$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_Q \ R_Q$
输出格式
示例评测程序在每次调用 max_prize 函数后，将该函数的返回值输出到标准输出的一行中。
数据范围
- $2 \le N \le 200\,000$
- $1 \le Q \le 500\,000$
- $0 \le X_i \le 10^9$ ($0 \le i \le N - 1$)
- $0 \le Y_i \le 10^9$ ($0 \le i \le N - 1$)
- $0 \le L_j < R_j \le N - 1$ ($1 \le j \le Q$)
- $R_j - L_j + 1$ 为偶数 ($1 \le j \le Q$)
- 给定值均为整数。
子任务
- (16 分) $Q \le 100, X_i \le 100, Y_i \le 100$ ($0 \le i \le N - 1$), $R_j - L_j + 1 \le 100$ ($1 \le j \le Q$)。
- (16 分) $Q \le 100, R_j - L_j + 1 \le 100$ ($1 \le j \le Q$)。
- (19 分) $Q \le 200\,000, L_j \le L_{j+1}, R_j \le R_{j+1}$ ($1 \le j \le Q - 1$)。
- (12 分) $N \le 20\,000, Q \le 50\,000$。
- (14 分) $N \le 100\,000, Q \le 200\,000$。
- (23 分) 无附加限制。
样例
输入格式 1
5 3 2 1 3 1 0 1 1 0 2 0 0 3 1 4 2 3
输出格式 1
2 0 2
说明
在第一次调用 max_prize 时，使用了袋子 $0, 1, 2, 3$。如果参与者按以下方式抽球，获得的奖品总数将为 $2$：
第一位参与者分别从袋子 $0, 1, 2, 3$ 中抽取了一个红球、一个蓝球、一个红球和一个蓝球。由于抽到的红球和蓝球数量相等，他们获得了一个奖品。
第二位参与者分别从袋子 $0, 1, 2, 3$ 中抽取了一个蓝球、一个红球、一个红球和一个蓝球。由于抽到的红球和蓝球数量相等，他们获得了一个奖品。
* 此时，袋子 $1$ 变空，抽奖活动结束。
参与者不可能获得超过 $2$ 个奖品。因此，第一次调用 max_prize 必须返回 $2$。
在第二次调用 max_prize 时，使用了袋子 $1, 2, 3, 4$。由于袋子 $4$ 从一开始就是空的，抽奖活动在没有任何参与者抽球的情况下结束。因此，第二次调用 max_prize 必须返回 $0$。
在第三次调用 max_prize 时，使用了袋子 $2, 3$。如果参与者按以下方式抽球，获得的奖品总数将为 $2$：
第一位参与者分别从袋子 $2, 3$ 中抽取了一个红球和一个红球。由于抽到的红球和蓝球数量不相等，他们没有获得奖品。
第二位参与者分别从袋子 $2, 3$ 中抽取了一个红球和一个蓝球。由于抽到的红球和蓝球数量相等，他们获得了一个奖品。
第三位参与者分别从袋子 $2, 3$ 中抽取了一个红球和一个蓝球。由于抽到的红球和蓝球数量相等，他们获得了一个奖品。
此时，袋子 $2$ 和 $3$ 变空，抽奖活动结束。
参与者不可能获得超过 $2$ 个奖品。因此，第三次调用 max_prize 必须返回 $2$。
该样例输入满足子任务 $1, 2, 4, 5$ 和 $6$ 的限制。
输入格式 2
6 5 1 3 3 2 1 0 1 2 1 1 2 1 0 1 1 2 1 4 2 5 4 5
输出格式 2
2 3 3 1 1
说明
该样例输入满足所有子任务的限制。