#2967. 「COCI 2010.03.06」PROGRAM

内存限制:32 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COCI 2010.03.06 T5「PROGRAM

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

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

Mirko 调用了 something\tt something 函数 KK 次,第 ii 次调用时 jump=Xi\tt jump= \it X_i

接下来有 QQ 次查询,每次查询包含两个整数 Li,L_i, RiR_i,对于每组查询请输出 i=LiRiseqi\displaystyle\sum_{i=L_i}^{R_i}\mathit{seq}_i

输入格式

第一行:N,KN,K
接下来一行 KK 个整数,第 ii 个为 XiX_i
N+2N+2 行:QQ
接下来 QQ 行:每行两个整数 Li,L_i, RiR_i

输出格式

QQ 行,第 ii 行包含第 ii 组查询的答案。

样例

样例输入 1

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

样例输出 1

35
18
3

样例说明 1

seq={4,3,4,3,4,3,4,3,4,3}seq=\{4, 3, 4, 3, 4, 3, 4, 3, 4, 3\}

样例输入 2

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

样例输出 2

8
2
1

样例说明 2

seq={3,0,0,1,0,0,1,1,0,1,1}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

样例输出 3

16422
28874

数据范围与提示

1N,K,Q106,1≤N,K,Q≤10^6, 1Xi<N,1≤X_i<N, 0LiRi<N0≤L_i≤R_i<N.