Problem Description

Translated from COCI 2010.03.06 T5 "PROGRAM"

Initially, the array seq is cleared to zero. Note that the first element of the seq array is indexed at 0, not 1.

void something (int jump) {
  for (int i = 0; i < N; i += jump)
    ++seq[i];
}

Mirko calls the something function K times, with the i-th call using jump = X_i.

There are Q queries following, each containing two integers L_i and R_i. For each query, output the sum of seq from index L_i to R_i.

Input Format

The first line contains two integers, N and K.
The next line contains K integers, where the i-th integer is X_i.
The N+2-th line contains an integer Q.
The following Q lines each contain two integers L_i and R_i.

Output Format

Output Q lines, where the i-th line contains the answer for the i-th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

35
18
3

Sample Input #2

11 3
3 7 10
3
0 10
2 6
7 7

Sample Output #2

8
2
1

Sample Input #3

1000000 6
12 3 21 436 2 19
2
12 16124
692 29021

Sample Output #3

16422
28874

Notes/Hints

Sample Explanation 1

seq = {4, 3, 4, 3, 4, 3, 4, 3, 4, 3}

Sample Explanation 2

seq = {3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}

Data Range and Hints

1 ≤ N, K, Q ≤ 10^6, 1 ≤ X_i < N, 0 ≤ L_i ≤ R_i < N.

见题面 Input 部分

见题面 Output 部分