Santa and Cookies

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

A little-known fact about Santa is that he hates having to eat cookies every time he delivers presents. More accurately, he likes cookies but thinks that the ones he has to eat have too much butter in them and not enough cheese.

This year, Mrs. Clause has helped him by giving him N cookbooks. The ith cookbook has a recipe that calls for anywhere between L_i to R_i blocks of cheese, inclusive.

Since Santa doesn't want to read all of these cookbooks, he makes you do it for him. To test your knowledge, Santa will ask you Q questions each containing an integer K_i. For each question, you must find the number of cookbooks that allow putting K_i blocks of cheese in the cookies.

Input Specification

The first line of input will contain two space-separated integers, N and Q (1 \le N, Q \le 10^5).

The next N lines will each contain two space-separated integers, L_i and R_i (1 \le L_i \le R_i \le 10^5).

The next Q lines will each contain one integer, K_i (1 \le K_i \le 10^5).

Output Specification

For each question, output the number of cookbooks that satisfy the above condition on a separate line.


Subtask 1 [20%]

1 \le N \le 10^3

Subtask 2 [80%]

No further constraints.

Sample Input

4 2
1 10
5 6
3 8
2 3

Sample Output


Explanation for Sample Output

For the first query, cookbooks 1, 2, and 3 allow using 6 blocks of cheese.

For the second query, only cookbook 1 allows using 9 blocks of cheese.


There are no comments at the moment.