F - Sum of Mod of Linear Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

整数 N,Q と長さ N の整数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。

Q 個のクエリが与えられるのでそれぞれについて答えてください。各クエリでは整数 x が与えられるので、\displaystyle \sum_{i=1}^N ((x+A_i) \bmod B_i) の値を求めてください。

制約

  • 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
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i は以下の形式で与えられる。

x

出力

Q 行出力せよ。

i 行目 (1\le i\le Q) には、\text{query}_i に対する答えを出力せよ。

入力例 1

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

出力例 1

3
5
4
1
2

各クエリに対する答えは以下のように求められます。

  • 1 番目のクエリでは x=0 なので、((0+1)\bmod 3)+((0+2)\bmod 5)+((0+0)\bmod 1)=1+2+0=3 です。
  • 2 番目のクエリでは x=1 なので、((1+1)\bmod 3)+((1+2)\bmod 5)+((1+0)\bmod 1)=2+3+0=5 です。
  • 3 番目のクエリでは x=2 なので、((2+1)\bmod 3)+((2+2)\bmod 5)+((2+0)\bmod 1)=0+4+0=4 です。
  • 4 番目のクエリでは x=3 なので、((3+1)\bmod 3)+((3+2)\bmod 5)+((3+0)\bmod 1)=1+0+0=1 です。
  • 5 番目のクエリでは x=200000 なので、((200000+1)\bmod 3)+((200000+2)\bmod 5)+((200000+0)\bmod 1)=0+2+0=2 です。

入力例 2

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

出力例 2

2
6
12
10

入力例 3

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

出力例 3

16
21
31
29
19
21
27

Score : 500 points

Problem Statement

You are given integers N,Q and integer sequences A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) of length N.

You are given Q queries, so answer each of them. In each query, you are given an integer x; find the value of \displaystyle \sum_{i=1}^N ((x+A_i) \bmod B_i).

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i is given in the following format:

x

Output

Print Q lines.

The i-th line (1\le i\le Q) should contain the answer to \text{query}_i.

Sample Input 1

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

Sample Output 1

3
5
4
1
2

The answer to each query is obtained as follows.

  • In the 1-st query, x=0, so the answer is ((0+1)\bmod 3)+((0+2)\bmod 5)+((0+0)\bmod 1)=1+2+0=3.
  • In the 2-nd query, x=1, so the answer is ((1+1)\bmod 3)+((1+2)\bmod 5)+((1+0)\bmod 1)=2+3+0=5.
  • In the 3-rd query, x=2, so the answer is ((2+1)\bmod 3)+((2+2)\bmod 5)+((2+0)\bmod 1)=0+4+0=4.
  • In the 4-th query, x=3, so the answer is ((3+1)\bmod 3)+((3+2)\bmod 5)+((3+0)\bmod 1)=1+0+0=1.
  • In the 5-th query, x=200000, so the answer is ((200000+1)\bmod 3)+((200000+2)\bmod 5)+((200000+0)\bmod 1)=0+2+0=2.

Sample Input 2

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

Sample Output 2

2
6
12
10

Sample Input 3

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

Sample Output 3

16
21
31
29
19
21
27