MIRKO 写了一段程序，并按如下方法运行这个程序。首先开了一个大小为N的数组，并赋值为零。接下来运行他的程序。程序如下：
C代码：
void something( int jump ) {
int i = 0;
while( i < N ) {
seq[open]i[close] = seq[open]i[close] + 1;
i = i + jump;
}
}
Pascal代码：
procedure something( jump: longint );
var i : longint;
begin
i := 0;
while i < N do
begin
seq[open]i[close] := seq[open]i[close] + 1;
i := i + jump;
end;
end;
每运行一次代码，他都会传入一个JUMP的值。一共运行了K次。传入的JUMP序列可表示为X1 X2 X3... Xk 。接下来，他通过Q个询问来来测试自己的程序是否正常工作。询问格式如下：L，R，表示输出数组中L到R的和，包括（L，R），你的程序要完成的就是顺次输出这Q的询问的值。
输入：
第一行两个正整数 N (1 ≤ N ≤ 10^6), 表示数组的大小，and K (1 ≤ K ≤ 10^6), 表示运行代码的次数。
第二行K个整数，表示传入的参数值: X1X2X3 ... Xk, (1 ≤ Xi < N).
接下来一行一个整数，Q (1 ≤ Q ≤ 10^6), 表示询问的次数。
接下来的Q行表示询问的边界Li i Ri(0 ≤ Li≤ Ri < N)。
输出：
共Q 行，每行一个数，表示对应的和。
样例：
Input:
10 4
1 1 2 1
3
0 9
2 6
7 7
Output:
35
18
3
Input:
11 3
3 7 10
3
0 10
2 6
7 7
Output:
8
2
1
Input:
1000000 6
12 3 21 436 2 19
2
12 16124
692 29021
Output:
16422
28874
样例说明：
样例1传入的参数是 1, 1, 2, 1.
运行后数组为{4, 3, 4, 3, 4, 3, 4, 3, 4, 3}2 to 6 的和为4+3+4+3+4=18.
样例2的数组为。{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}.