问题描述

一条数线上有 $N$ 个村庄。第 $i$ 个村庄位于坐标 $X_i$，并且有 $P_i$ 个村民。

回答 $Q$ 个查询。第 $i$ 个查询的格式如下:

• 给定整数 $L_i$ 和 $R_i$，求位于坐标 $L_i$ 和 $R_i$ 之间的村庄中居住的村民总数，包括 $L_i$ 和 $R_i$。

数据规模

$1\leq N,Q\leq 2×10^5$

$-10^9\leq X_1<X_2<\ldots<X_N\leq 10^9$

$1\leq P_i\leq 10^9$

$-10^9\leq L_i\leq R_i\leq 10^9$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$N$

$X_1 \ldots X_N$

$P_1 \ldots P_N$

$Q$

$L_1\ R_1$

$\vdots$

$L_Q\ R_Q$

输出

打印 $Q$ 行。

第 $i(1≤i≤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