Debug

Seán is debugging his own code. He first creates an array seq of $N$ integers and fills it with zeros. He then calls the following C++ function several times.

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

The function adds 1 to every element whose index is a multiple of jump. Index 0 is a multiple of every jump, so seq[0] grows by 1 on every call.

Seán calls the function exactly $K$ times and passes $X_1, X_2, \dots, X_K$ in that order.

Once the calls are done, Seán picks $Q$ parts of the array he wants to check. Each part is given by its left bound $L$ and its right bound $R$ ($L \le R$). For each part, compute seq[L] + seq[L+1] + ... + seq[R].

The first line contains the array size $N$ and the number of calls $K$ ($1 \le N \le 10^6$, $1 \le K \le 10^6$).

The second line contains the $K$ arguments $X_1, X_2, \dots, X_K$ separated by spaces ($1 \le X_i < N$).

The third line contains the number of parts $Q$ ($1 \le Q \le 10^6$).

Each of the next $Q$ lines contains two integers $L_i$ and $R_i$ ($0 \le L_i \le R_i < N$).

Print $Q$ lines. Line $i$ holds the value of seq[L_i] + seq[L_i + 1] + ... + seq[R_i].