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~.
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~.
For each query, print the sum of the number of stones in each of the cups in the range ~[a, b]~, inclusive.
5 3 1 1 2 2 0 2 2 4