## 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

^{9}..10

^{9}], and

*Q*(0 ≤ Q ≤ 100000) queries of the form "

*how many intervals contain this integer*" (where -2 × 10

*x*?^{9}≤

*x*≤ 2 × 10

^{9}). 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)

bbi5291on Dec 19, 2008 - 7:28:37 pm UTC Hinttaimla101on Dec 07, 2008 - 6:25:40 pm UTC How many queries are there at maxbbi5291on Dec 07, 2008 - 7:27:11 pm UTC Re: How many queries are there at max