题目描述

译自 COCI 2010.03.06 T5. PROGRAM

开始时，$\mathit{seq}$ 数组已清零。请注意 $\mathit{seq}$ 数组的第一个元素的下标是 $0$ 而非 $1$。

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

Mirko 调用了 $\tt something$ 函数 $K$ 次，第 $i$ 次调用时 $\tt jump = \it X_i$。

接下来有 $Q$ 次查询，每次查询包含两个整数 $L_i, R_i$，对于每组查询请输出

$$\displaystyle\sum_{i=L_i}^{R_i}\mathit{seq}_i$$

---

输入格式

第一行：$N,K$。 接下来一行 $K$ 个整数，第 $i$ 个为 $X_i$。 第 $N+2$ 行：$Q$。 接下来 $Q$ 行：每行两个整数 $L_i, R_i$。

---

输出格式

共 $Q$ 行，第 $i$ 行包含第 $i$ 组查询的答案。

---

样例 1

输入：

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

输出：

35
18
3

解释：$\mathit{seq}=\{4, 3, 4, 3, 4, 3, 4, 3, 4, 3\}$

---

样例 2

输入：

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

输出：

8
2
1

解释：$\mathit{seq}=\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}$

---

样例 3

输入：

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

输出：

16422
28874

---

数据范围与提示

$1≤N,K,Q≤10^6, 1≤X_i<N, 0≤L_i≤R_i<N.$