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 (he is such a good coder he coded it in both C++ and Pascal):

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

procedure something( jump: longint );
var i : longint;
begin
    i := 0;
    while i < N do
    begin
        seq[i] := seq[i] + 1;
        i := i + jump;
    end;
end;

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\ X_3 \ldots 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] + \text{seq}[L+2] + \ldots + \text{seq}[R]\). Since he needs to know the answer in advance in order to check it, he asked you to help him.

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\ X_3 \ldots X_K\), arguments passed to the procedure (\(1 \le X_i < N\)).

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

The 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.

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] + \text{seq}[L_i+2] + \ldots + \text{seq}[R_i]\).

First sample description: 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\).

Second sample description: The array is \(\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}\).

riseoj 작성

출처 COCI 2009/2010 Contest 5