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 (1 ≤ n ≤ 106
). Second line contains number of days m (1 ≤ m ≤ 106
). Each of the next m lines consists of two space separated integers l and r (1 ≤ l ≤ r ≤ n). Followed number is the number of queries q (1 ≤ q ≤ 106
). Each of next q lines contain a single integer x (1 ≤ x ≤ n).
Output
For each query output the result in a new line.
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