Intervals

A closed interval [a..b] contains the integers a, a+1, a+2, ... b-2, b-1, b. You are given N closed intervals [a_i..b_i] (0 ≤ N ≤ 100000), with a_i and b_i in the range [-10⁹..10⁹], and Q (0 ≤ Q ≤ 100000) queries of the form "how many intervals contain this integer x?" (where -2 × 10⁹ ≤ x ≤ 2 × 10⁹). Determine the answer to each query.

Input Format
Line 1: Two space-separated integers, N and Q
Next N lines: Two space-separated integers each, a_i and b_i, denoting one closed interval.
Next Q lines: One integer each, denoting a single query.

Output Format
Print the answer to each query on its own line.

Sample Input

3 10
0 3
2 4
3 7
-1
0
1
2
3
4
5
6
7
8

Sample Output

0
1
1
2
3
2
1
1
1
0

Note: In test cases worth 25% of the points, a_i and b_i will be in the range [-1000..1000].

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 5.00s
Memory Limit: 16M
Added: Dec 05, 2008
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)