P5190 [COCI 2009/2010 #5] PROGRAM

**译自 [COCI 2010.03.06](http://hsin.hr/coci/archive/2009_2010/) T5「[PROGRAM](http://hsin.hr/coci/archive/2009_2010/contest5_tasks.pdf)」** 开始时，$\mathit{seq}$ 数组已清零。请注意 $\mathit{seq}$ 数组的第一个元素的下标是 0 而非 1。 ```cpp 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 $seq=\{4, 3, 4, 3, 4, 3, 4, 3, 4, 3\}$ #### 样例说明 2 $seq=\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}$ #### 数据范围与提示 $1≤N,K,Q≤10^6,$ $1≤X_i