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 1\,000\,000)~ 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 1\,000\,000)~ 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