一维国度

题目描述

数轴上有 $N$ 个村庄。第 $i$ 个村庄位于坐标 $X_i$，有 $P_i$ 个村民。

回答 $Q$ 个询问。第 $i$ 个询问的格式如下：

给定整数 $L_i$ 和 $R_i$，求位于坐标 $L_i$ 和 $R_i$ 之间（含端点）的村庄中村民的总数。

输入格式

输入按以下格式从标准输入给出：

$N$
$X_1$ $\ldots$ $X_N$
$P_1$ $\ldots$ $P_N$
$Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$

输出格式

输出 $Q$ 行。

第 $i$ 行 $(1 \le i \le Q)$ 应包含第 $i$ 个询问的答案。

样例

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

1
5
10
0

考虑第一个询问。位于坐标 $1$ 和 $1$ 之间的村庄是坐标 $1$ 处的村庄，有 $1$ 个村民。因此答案是 $1$。

考虑第二个询问。位于坐标 $2$ 和 $6$ 之间的村庄是坐标 $3$ 和 $5$ 处的村庄，分别有 $2$ 和 $3$ 个村民。因此答案是 $2+3=5$。

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

26
15
7
26
18
28
26
11

数据范围

• $1 \le N, Q \le 2 \times 10^5$
• $-10^9 \le X_1 \lt X_2 \lt \ldots \lt X_N \le 10^9$
• $1 \le P_i \le 10^9$
• $-10^9 \le L_i \le R_i \le 10^9$
• 输入中的所有数值均为整数