在另一个平行宇宙中，Vlad 被困在未来版的 Poenari 城堡中。该城堡共有 $n$ 层，编号为 $0$ 到 $n - 1$。从每一层 $i$（$0 \le i \le n - 1$）开始，他只能向上走。他可以走楼梯并支付 $1$ 滴血（这是罗马尼亚吸血鬼使用的货币），或者化身为蝙蝠穿过通风管道，为此他必须支付 $2$ 滴血。楼梯最多可以带他向上移动 $v[i]$ 层，而通风管道最多可以带他向上移动 $w[i]$ 层。其中 $v$ 和 $w$ 是给定的两个数组：$v = [v[0], v[1], \dots, v[n - 1]]$ 且 $w = [w[0], w[1], \dots, w[n - 1]]$。

形式化地，从楼层 $i$（$0 \le i \le n - 1$）出发，Vlad 可以：

• 在不超过 $n - 1$ 的前提下，到达从楼层 $i + 1$ 到 $i + v[i]$ 的任意楼层，花费为 $1$。
• 在不超过 $n - 1$ 的前提下，到达从楼层 $i + 1$ 到 $i + w[i]$ 的任意楼层，花费为 $2$。

此外，他的兄弟 Radu 和 Mircea 为 Vlad 提出了 $m$ 个场景，每个场景由两个楼层 $A$ 和 $B$（$A \le B$）组成。Vlad 必须回答他们的 $m$ 个问题：从楼层 $A$ 到楼层 $B$ 他最少需要牺牲多少滴血？

实现细节

你需要实现函数 solve：

std::vector<int> solve(std::vector<int> &v, std::vector<int> &w, 
                       std::vector<std::pair<int,int>> &queries);

• 接收向量 v（从每个楼层出发的楼梯高度）和 w（从每个楼层出发的通风管道系统高度），两者的长度均为 $n$。
• 同时接收询问 queries，这是一个大小为 $m$ 的由 pair 组成的向量。每个 pair 包含题面中所述的 $A$ 和 $B$。
• 返回一个大小为 $m$ 的向量，由这 $m$ 个询问的答案组成。

数据范围

• $1 \le n, m \le 500\,000$。
• $1 \le v[i], w[i] \le n$ 对于所有 $0 \le i \le n - 1$。
• $0 \le A \le B \le n - 1$ 对于所有询问。

子任务

1. (5 分) $1 \le n \le 300$，$1 \le m \le 500\,000$
2. (7 分) $1 \le n \le 3\,000$，$1 \le m \le 3\,000$
3. (11 分) $1 \le n \le 20\,000$，$1 \le m \le 20\,000$
4. (44 分) $1 \le n \le 200\,000$，$1 \le m \le 200\,000$
5. (8 分) $1 \le n \le 500\,000$，$1 \le m \le 500\,000$，且对于所有 $0 \le i < j \le n - 1$，有 $v[i] \le v[j]$ 且 $w[i] \le w[j]$。
6. (25 分) 无附加限制。

样例

输入样例 1

7
2 3 1 1 1 1 2
3 4 1 2 1 2 2
3
0 4
0 5
0 6

输出样例 1

2
3
4

说明 1

考虑以下调用：

solve({2, 3, 1, 1, 1, 1, 2}, {3, 4, 1, 2, 1, 2, 2}, {{0, 4}, {0, 5}, {0, 6}})

这里我们有 $n = 7$ 和 $3$ 个询问，$v = [2, 3, 1, 1, 1, 1, 2]$ 且 $w = [3, 4, 1, 2, 1, 2, 2]$。

对于第一个询问 $(0, 4)$，Vlad 必须进行两次代价为 $1$ 的跳跃：从 $0$ 到 $1$（尽管他可以跳到 $2$，但从楼层 $1$ 出发可以让他走得更远），然后从 $1$ 到 $4$。总代价：$1 + 1 = 2$。

对于第二个询问 $(0, 5)$，有 $2$ 条最优路径：从 $0$ 到 $1$（代价 $1$），从 $1$ 到 $4$（代价 $1$），从 $4$ 到 $5$（代价 $1$）；第二条路径是从 $0$ 到 $1$（代价 $1$），从 $1$ 到 $5$（代价 $2$）。总代价：$1 + 1 + 1 = 1 + 2 = 3$。

对于第三个询问 $(0, 6)$，一个代价为 $4$ 的示例路径是从 $0$ 到 $1$（代价 $1$），从 $1$ 到 $5$（代价 $2$），从 $5$ 到 $6$（代价 $1$）。总代价：$1 + 2 + 1 = 4$。

因此函数返回的 vector 必须为：{2, 3, 4}。

输入样例 2

10
1 1 1 2 3 2 1 1 2 3
2 4 1 4 1 4 1 3 2 3
5
3 9
0 9
0 7
0 4
3 5

输出样例 2

3
5
4
3
1

说明 2

考虑以下调用：

solve({1, 1, 1, 2, 3, 2, 1, 1, 2, 3}, {2, 4, 1, 4, 1, 4, 1, 3, 2, 3}, {{3, 9}, {0, 9}, {0, 7}, {0, 4}, {3, 5}})

这些是询问的最优路径：

• $(3,9)$：从 $3$ 到 $5$（代价 $1$），从 $5$ 到 $9$（代价 $2$） $\implies$ 总计：$3$
• $(0,9)$：从 $0$ 到 $1$（代价 $1$），从 $1$ 到 $5$（代价 $2$），从 $5$ 到 $9$（代价 $2$） $\implies$ 总计：$5$
• $(0,7)$：从 $0$ 到 $1$（代价 $1$），从 $1$ 到 $5$（代价 $2$），从 $5$ 到 $7$（代价 $1$） $\implies$ 总计：$4$
• $(0,4)$：从 $0$ 到 $1$（代价 $1$），从 $1$ 到 $4$（代价 $2$） $\implies$ 总计：$3$
• $(3,5)$：从 $3$ 到 $5$（代价 $1$） $\implies$ 总计：$1$

因此函数返回的 vector 必须为：{3, 5, 4, 3, 1}。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 1 行：$n$
• 第 2 行：$v[0]\ v[1]\ \dots\ v[n - 1]$
• 第 3 行：$w[0]\ w[1]\ \dots\ w[n - 1]$
• 第 4 行：$m$
• 第 $5 + i$ 行（$0 \le i \le m - 1$）：$A\ B$

并输出 $m$ 行，即调用 solve 的结果。