Mirko is trying to debug a piece of his code. First he creates an array of ~N~ integers and fills it with zeros. Then he repeatedly calls the following procedure:

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

As you can see, this procedure increases by one all elements in the array whose indices are divisible by jump.

Mirko calls the procedure exactly ~K~ times, using the sequence ~X_1\ X_2 \dots X_k~ as arguments.

After this, Mirko has a list of ~Q~ special parts of the array he needs to check to verify that his code is working as it should be. Each of these parts is defined by two numbers, ~L~ and ~R~ ~(L \le R)~ the left and right bound of the special part. To check the code, Mirko must compute the sum of all elements of seq between and including ~L~ and ~R~. In other words ~\text{seq}[L] + \text{seq}[L+1] + \dots + \text{seq}[R]~. Since he needs to know the answer in advance in order to check it, he asked you to help him.

Input Specification

The first line of input contains two integers, ~N~ ~(1 \le N \le 10^6)~, size of the array, and ~K~ ~(1 \le K \le 10^6)~, number of calls to something Mirko makes.

The second line contains ~K~ integers: ~X_1, X_2, \dots, X_k~ ~(1 \le X_i < N)~, arguments passed to the procedure.

Next line contains one integer ~Q~ ~(1 \le Q \le 10^6)~, number of special parts of the array Mirko needs to check.

Next ~Q~ lines contain two integers each ~L_i~ and ~R_i~ ~(0 \le L_i \le R_i < N)~, bounds of each special part.

Output Specification

The output should contain exactly ~Q~ lines. The ~i~th line should contain the sum of elements ~\text{seq}[L_i] + \text{seq}[L_i+1] + \dots + \text{seq}[R_i]~.

Sample Input 1

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

Sample Output 1

35
18
3

Explanation for Sample Output 1

The procedure is called with arguments ~1~, ~1~, ~2~, ~1~. After that, the array contains values ~\{4, 3, 4, 3, 4, 3, 4, 3, 4, 3\}~. Sum of indices ~2~ to ~6~ (inclusive) is ~4+3+4+3+4 = 18~.

Sample Input 2

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

Sample Output 2

8
2
1

Explanation for Sample Output 2

The array is ~\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}~.

Sample Input 3

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

Sample Output 3

16422
28874