Mirko 正在尝试调试他的一段代码。首先，他创建了一个大小为 $N$ 的整数数组，并将其初始化为全 $0$。然后，他重复调用以下过程（他是一个非常优秀的程序员，所以他用 C++ 和 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;

如你所见，该过程会将数组中所有下标能被 jump 整除的元素的值加 $1$。

Mirko 总共调用了该过程恰好 $K$ 次，依次传入序列 $X_1, X_2, X_3, \dots, X_K$ 中的元素作为参数。

在此之后，Mirko 得到了一个包含 $Q$ 个待查询区间的列表，他需要通过这些区间来验证他的代码是否正常工作。每个区间由两个数 $L$ 和 $R$（$L \le R$）定义，分别表示该区间的左右边界。为了验证代码，Mirko 必须计算 $\text{seq}$ 数组中从 $L$ 到 $R$（包含端点）的所有元素之和。换句话说，即计算 $\text{seq}[L] + \text{seq}[L+1] + \text{seq}[L+2] + \dots + \text{seq}[R]$。由于他需要提前知道答案以便进行比对，他请求你来帮助他。

输入格式

第一行包含两个整数 $N$（$1 \le N \le 10^6$），表示数组的大小，以及 $K$（$1 \le K \le 10^6$），表示 Mirko 调用该过程的次数。

第二行包含 $K$ 个整数 $X_1, X_2, X_3, \dots, X_K$，表示传递给该过程的参数（$1 \le X_i < N$）。

第三行包含一个整数 $Q$（$1 \le Q \le 10^6$），表示 Mirko 需要检查的区间数量。

接下来的 $Q$ 行，每行包含两个整数 $L_i$ 和 $R_i$（$0 \le L_i \le R_i < N$），表示每个待检查区间的边界。

输出格式

输出应当包含恰好 $Q$ 行。第 $i$ 行应当包含区间和 $\text{seq}[L_i] + \text{seq}[L_i+1] + \text{seq}[L_i+2] + \dots + \text{seq}[R_i]$。

样例

输入样例 1

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

输出样例 1

35
18
3

输入样例 2

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

输出样例 2

8
2
1

输入样例 3

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

输出样例 3

16422
28874

说明

样例 1 说明：该过程被调用时传入的参数依次为 $1, 1, 2, 1$。调用结束后，数组中的值为 $\{4, 3, 4, 3, 4, 3, 4, 3, 4, 3\}$。下标从 $2$ 到 $6$（包含端点）的元素之和为 $4+3+4+3+4 = 18$。

样例 2 说明：调用结束后，数组中的值为 $\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}$。