公司最近借助日益流行的编程测试，开始制作编程测试题并销售给 IT 企业。

为了方便，公司将题目的难度划分为从 $0$ 级到 $N-1$ 级。目前，公司中已经准备了 $A[i]$ 道被评为难度 $i$ 级的题目；此外，还有 $B[i]$ 道题目由于难度界定模糊，被评为难度 $i$ 级或者 $i+1$ 级。不存在其他方式评定难度的题目。

公司现在正在寻找购买题目的企业。目前一共有 $M$ 家企业表示了购买意向，编号为 $0$ 到 $M-1$。编号为 $j$（$0 \le j \le M-1$）的企业只对难度在 $L[j]$ 级以上、$U[j]$ 级以下的题目感兴趣。

当公司向第 $j$ 家企业销售题目时，会从难度 $L[j]$ 到 $U[j]$ 的每一个难度级别中各选一道题目，打包成一个集合进行出售。我们称其为一个套装。

如果只向第 $j$ 家企业出售题目，最多可以出售多少个套装？

对于被评为难度 $i$ 级或 $i+1$ 级的题目，应当适当选择其具体难度，使得可出售的套装数量最大。同时，在所有出售的套装中，同一道题目不能被重复使用。

实现细节

你需要实现下面的函数：

vector<int> testset(vector<int> A, vector<int> B, vector<int> L, vector<int> U)

• 该函数只会被调用一次。
• A：长度为 $N$ 的整数数组。对所有 $i$（$0 \le i \le N-1$），$A[i]$ 表示被评为难度 $i$ 级的题目数量。
• B：长度为 $N-1$ 的整数数组。对所有 $i$（$0 \le i \le N-2$），$B[i]$ 表示被评为难度 $i$ 级或 $i+1$ 级的题目数量。
• L, U：长度为 $M$ 的整数数组。对所有 $j$（$0 \le j \le M-1$），$L[j]$ 和 $U[j]$ 分别表示第 $j$ 家企业希望的最小和最大题目难度。
• 该函数需要返回一个长度为 $M$ 的整数数组 $S$。对所有 $j$（$0 \le j \le M-1$），$S[j]$ 表示可以向第 $j$ 家企业出售的、由难度 $L[j]$ 到 $U[j]$ 题目组成的套装的最大数量。

提交的源代码中任何部分都不允许执行输入输出函数。

样例数据

考虑如下情况：

• $N = 4$
• $M = 2$
• $A = [2, 3, 1, 1]$
• $B = [1, 3, 2]$
• $L = [0, 1]$
• $U = [3, 2]$

评测程序将如下方式调用函数：

testset({2, 3, 1, 1}, {1, 3, 2}, {0, 1}, {3, 2})

第 0 家企业希望购买难度在 $0$ 级到 $3$ 级之间的题目。可以用如下方式组成 $3$ 个套装，此时仅剩下一道难度为 $1$ 级的题目，无法再组成新的套装。

第 1 家企业希望购买难度在 $1$ 级到 $2$ 级之间的题目。可以用如下方式组成 $5$ 个套装，并且已经用完所有可用题目，无法再组成新的套装。

因此，testset 函数应返回 $S = [3, 5]$。

限制

• $2 \le N \le 100,000$
• $1 \le M \le 100,000$
• $0 \le A[i] \le 10^8$（$0 \le i \le N-1$）
• $0 \le B[i] \le 10^8$（$0 \le i \le N-2$）
• $0 \le L[j] \le U[j] \le N-1$（$0 \le j \le M-1$）

子任务

1. （3 分）$A[i] \le 1,000$（$0 \le i \le N-1$），$B[i] \le 1,000$（$0 \le i \le N-2$），且 $U[j] - L[j] \le 2$（$0 \le j \le M-1$）
2. （15 分）$M \le 100$
3. （36 分）$N \le 5,000$
4. （23 分）对所有 $0 \le j \le M-1$，$L[j] = 0$
5. （23 分）无额外限制

样例评测器

样例评测器的输入格式如下：

• 第 1 行：$N\ M$
• 第 2 行：$A[0]\ A[1]\ \cdots\ A[N-1]$
• 第 3 行：$B[0]\ B[1]\ \cdots\ B[N-2]$
• 第 $4+j$ 行（$0 \le j \le M-1$）：$L[j]\ U[j]$

样例评测器的输出格式如下：

• 第 $1+j$ 行（$0 \le j \le M-1$）：$S[j]$