Program

Time limit2sMemory limit256 MB

Summary

Simulate marking multiples of several jump values into an array using a difference/counting trick, then answer many range-sum queries with prefix sums.

Level: Medium6 of 10
Topics: Prefix sum, Array, Math
Solved: No attempts yet

Problem

Changyoung is debugging a program to find an error. The program creates an array a of size N filled entirely with zeros, and then calls the something function shown below.

void something(int jump) {
    int i = 0;
    while (i < N) {
        a[i] = a[i] + 1;
        i = i + jump;
    }
}

Changyoung calls this function K times. On each call, the jump argument is, in order, X1, X2, X3, …, XK.

In other words, calling something(X) increases by 1 the value at every index that is a multiple of X and smaller than N, that is, indices 0, X, 2X, 3X, ….

After all the calls, Changyoung checks whether the values were stored correctly. He performs Q checks in total; for each check he picks two integers L and R (L ≤ R) and computes the sum over that range, that is, a[L] + a[L+1] + … + a[R].

Given the X values used for the calls and the check parameters, write a program that outputs the result (the range sum) of each check.

Input

The first line contains the array size N and the number of function calls K. (1 ≤ N, K ≤ 10^6)

The second line contains the arguments X1, X2, …, XK used for the calls, separated by spaces. (1 ≤ Xi < N)

The third line contains the number of checks Q. (1 ≤ Q ≤ 10^6)

Each of the next Q lines contains two integers L and R used for one check. (0 ≤ L ≤ R < N)

Output

Print Q lines in total. For each check with its L and R, print the value of a[L] + a[L+1] + … + a[R].

Examples3

Example 1
Input
```
10 4
1 1 2 1
3
0 9
2 6
7 7
```
Expected output
```
35
18
3
```
Example 2
Input
```
11 3
3 7 10
3
0 10
2 6
7 7
```
Expected output
```
8
2
1
```

Example 3

Input

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

Expected output

16422
28874