### COCI 2009/2010, Contest #5

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 X1 X2 X3 ... Xk 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 ≤ 106), size of the array, and K (1 ≤ K ≤ 106), the number of calls to `something` Mirko makes.

The second line contains K integers: X1 X2 X3 ... Xk, arguments passed to the procedure. (1 ≤ Xi < N).

The next line contains one integer Q (1 ≤ Q ≤ 106), number of special parts of the array Mirko needs to check.

The next Q lines contain two integers each Li and Ri (0 ≤ Li ≤ Ri < N), bounds of each special part.

### Output

The output should contain exactly Q lines. The ith line should contain the sum of elements `seq`[Li] + `seq`[Li+1] + `seq`[Li+2] + ... + `seq`[Ri].

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

```35
18
3```

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

```8
2
1```

### Input

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

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

### Sample 2 Descrption

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

Point Value: 10 (partial)
Time Limit: 5.00s
Memory Limit: 32M