Seán 正在尝试调试他的一段代码。首先，他创建了一个包含 $N$ 个整数的数组，并将其全部初始化为零。然后，他重复调用以下用 C++ 编写的函数：

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

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

Seán 正好调用了该函数 $K$ 次，依次使用序列 $X_1, X_2, X_3, \dots, X_K$ 作为参数。

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

输入格式

输入的第一行包含两个整数 $N$ ($1 \le N \le 10^6$) 和 $K$ ($1 \le K \le 10^6$)，分别表示数组的大小以及 Seán 调用 something 函数的次数。

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

第三行包含一个整数 $Q$ ($1 \le Q \le 10^6$)，表示 Seán 需要检查的特定区间数量。

接下来的 $Q$ 行，每行包含两个整数 $L_i$ 和 $R_i$ ($0 \le L_i \le R_i < N$)，表示每个特定区间的边界。

输出格式

输出应正好包含 $Q$ 行。第 $i$ 行应包含区间内元素之和 seq[L_i] + seq[L_i + 1] + seq[L_i + 2] + ... + 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}。