Vincent Massey SS - 2014 Senior Contest #1

Lil' Jami is playing with a set of $N$ cups numbered $0,1,\dots ,N-1$ and an infinite number of stones. Each cup initially has $0$ stones in it. Since he has an infinite amount of free time, Lil' Jami plays a game where he repeatedly adds a stone to a cup. He does this $k$ times.

Following this, there will be $Q$ queries $(1\le Q\le 1000000)$ of the form a b $(0\le a\le b<N)$. For each query, find the sum of the stones in cups numbered $a,a+1,\dots ,b-1,b$.

Input Specification

The first line will contain the integers $N$ and $K$ $(1\le N,K\le 1000000)$ separated by a space.
The next $K$ lines will each contain a single integer $k_i$ $(0\le k_i<N)$ meaning to add a stone to the cup with index $k_i$ (for $0\le i<N$).
The next line will contain the single integer $Q$.
The next $Q$ lines will contain two space-separated integers $a$ and $b$.

Output Specification

For each query, print the sum of the number of stones in each of the cups in the range $[a,b]$, inclusive.

Sample Input

5 3
1
1
2
2
0 2
2 4

Sample Output

3
1