线性取模之和

题目描述

给定整数 $N,Q$ 以及长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$、$B=(B_1,B_2,\ldots,B_N)$。

有 $Q$ 个询问，请分别回答。每个询问给定一个整数 $x$，求

输入格式

输入第一行为一个整数 $N$。

接下来 $N$ 行，第 $i$ 行为两个整数 $A_i,B_i$。

接下来一行为一个整数 $Q$。

接下来 $Q$ 行，第 $i$ 行为一个整数 $x$。

输出格式

输出 $Q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

3
1 3
2 5
0 1
5
0
1
2
3
200000

3
5
4
1
2

样例 1 解释

• 第 $1$ 个询问 $x=0$：$((0+1)\bmod 3)+((0+2)\bmod 5)+((0+0)\bmod 1)=1+2+0=3$；
• 第 $2$ 个询问 $x=1$：$2+3+0=5$；
• 第 $3$ 个询问 $x=2$：$0+4+0=4$；
• 第 $4$ 个询问 $x=3$：$1+0+0=1$；
• 第 $5$ 个询问 $x=200000$：$0+2+0=2$。

3
2 3
5 7
0 9
4
9
3
6
17

2
6
12
10

8
0 10
3 8
1 3
5 7
4 8
4 9
2 6
5 7
7
130140
70510
22719
104735
119072
127841
191631

16
21
31
29
19
21
27

数据范围

对于所有测试数据，保证：

• $1 \le N \le 5 \times 10^5$；
• $0 \le A_i < B_i \le 5 \times 10^5$；
• $1 \le Q \le 2 \times 10^5$；
• $0 \le x \le 5 \times 10^5$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。