eolymp
Problems

Roy and Coin Boxes

Roy and Coin Boxes

Roy has n coin boxes numbered from 1 to n. Every day he selects two indices [l,r] and adds 1 coin to each coin box starting from l to r (both inclusive). He does this for m number of days.

After m days, Roy has a query: How many coin boxes have at least x coins. He has q such queries.

Input

First line contains number of coin boxes n (1n106). Second line contains number of days m (1m106). Each of the next m lines consists of two space separated integers l and r (1lrn). Followed number is the number of queries q (1q106). Each of next q lines contain a single integer x (1xn).

Output

For each query output the result in a new line.

Time limit 1 second
Memory limit 128 MiB
Input example #1
7
4
1 3
2 5
1 2
5 6
4
1
7
4
2
Output example #1
6
0
0
4