该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有一个叫 Socuo 的 Alien 在宠物医院工作来维持生计。 每天早上他会处理 K 个收到 的请求 Pi，每一个请求表示从 0 号格子开始，每隔 Pi 个宠物箱放入一个宠物。 每天下午 有畜牧兽疫局的人来检查宠物医院的动物密度。所谓的动物密度，也就是连续一段宠物箱内 宠物数量总和与这段宠物箱个数的比值。 现在，畜牧兽疫局的工作人员给出了 M 个检查， 显然他已经知道了有多少个宠物箱，所以只要你帮他处理这 M 个检查对应的宠物数量总和 即可。

Format

Input

第一行两个数 N, K，表示一共有 N 个宠物箱，K 个请求。

第二行 K 个数 Pi，表示这 K 个早上收到的请求。

第三行一个数 M，表示有 M 个检查。

接下来 M 行，每行两个数 Li, Ri，表示第 i 个检查是从 Li 到 Ri 的这一段宠物箱

Output

共 M 行，每行一个数 Reti，表示第 i 个检查对应的宠物数量总和

Samples

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

8
2
1

Sample Descriptions

经过 3 个请求，变成

[3 0 0 1 0 0 1 1 0 1 1]
 0 1 2 3 4 5 6 7 8 9 1

Limitation

对于 20%数据 N≤10000

对于 40%数据 M≤1000

对于 100%数据 N,K,M≤10^6,0<Pi<N, 0≤Li,R