Lil' Jami

View as PDF

Submit solution

Points: 7
Time limit: 1.4s
Memory limit: 16M

Author:
Problem type
Vincent Massey SS - 2014 Senior Contest #1

Lil' Jami is playing with a set of N cups numbered 0, 1, \ldots, 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, \ldots, 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

Comments

There are no comments at the moment.