P5190 [COCI 2009/2010 #5] PROGRAM

**Translated from [COCI 2010.03.06](http://hsin.hr/coci/archive/2009_2010/) T5 “[PROGRAM](http://hsin.hr/coci/archive/2009_2010/contest5_tasks.pdf)”.** At the beginning, the array $\mathit{seq}$ is all zeros. Note that the first element of $\mathit{seq}$ has index 0, not 1. ```cpp 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$.

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 $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

#### 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