Incremental Sequence Queries

This problem is adapted from COCI 2010.03.06 T5 "PROGRAM". Initially, an array seq of length N is filled with zeros. Note that the array indexing starts at 0.

A function something is defined as follows:

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

Mirko calls the function something exactly K times. In the i-th call, jump = X_i. After these calls, there are Q queries. Each query contains two integers \(L_i\) and \(R_i\). For each query, you need to output the sum:

$$\sum_{i=L}^{R} seq_i$$

where the summation is taken over the indices from L to R (inclusive).

inputFormat

The first line contains three integers: N, K, and Q.

The second line contains K integers: \(X_1, X_2, \dots, X_K\), representing the jump values for each call.

The following Q lines each contain two integers: L and R, denoting a query.

outputFormat

For each query, output a single integer: the sum of seq from index L to index R (inclusive).

sample

10 2 2
2 3
0 9
1 3

9
2

</p>