Problem Description

Translated from COCI 2010.03.06 T5 “PROGRAM”.

At the beginning, the array $\mathit{seq}$ is all zeros. Note that the first element of $\mathit{seq}$ has index 0, not 1.

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

Mirko called the function $\tt something$ exactly $K$ times. In the $i$-th call, $\tt jump = \it X_i$.

Then there are $Q$ queries. Each query contains two integers $L_i,$ $R_i$. For each query, output $\displaystyle\sum_{i=L_i}^{R_i}\mathit{seq}_i$.

Input Format

The first line contains $N, K$.
The next line contains $K$ integers, where the $i$-th one is $X_i$.
Line $N + 2$ contains $Q$.
The next $Q$ lines each contain two integers $L_i,$ $R_i$.

Output Format

Output $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

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

35
18
3

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

8
2
1

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

16422
28874

Hint

Sample Explanation 1

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

Sample Explanation 2

$seq=\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}$

Constraints

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

Translated by ChatGPT 5