PEG Judge - COCI09 #5

COCI 2009/2010, Contest #5

Task PROGRAM

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₁ X₂ X₃ ... 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 this parts is defined by two numbers, L and R (L ≤ 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 seq[L] + seq[L+1] + seq[L+2] + ... + seq[R]. Since he needs to know the answer in advance in order to check it, he asked you to help him.

Input

The first line of input contains two integers, N (1 ≤ N ≤ 10⁶), size of the array, and K (1 ≤ K ≤ 10⁶), the number of calls to something Mirko makes.

The second line contains K integers: X₁ X₂ X₃ ... X_k, arguments passed to the procedure. (1 ≤ X_i < N).

The next line contains one integer Q (1 ≤ Q ≤ 10⁶), 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 ≤ L_i ≤ R_i < N), bounds of each special part.

Output

The output should contain exactly Q lines. The i^th line should contain the sum of elements seq[L_i] + seq[L_i+1] + seq[L_i+2] + ... + seq[R_i].

Sample Tests

Input

Output

35
18
3

Input

Output

8
2
1

Input

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

Output

16422
28874

Sample 1 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}. The sum of indices 2 to 6 (inclusive) is 4 + 3 + 4 + 3 + 4 = 18.