Roy and Coin Boxes#5071
Roy has coin boxes numbered from to . Every day, he selects two indices and (1 \le l \le r \le n) and adds coin to each coin box from to (both inclusive). He repeats this operation for days.
After days, Roy has queries. For each query, given an integer , he wants to know: how many coin boxes have at least coins?
The first line contains an integer (1 \le n \le 10^6), the number of coin boxes.
The second line contains an integer (1 \le m \le 10^6), the number of days.
Each of the next lines contains two integers and (1 \le l \le r \le n), indicating that on that day, Roy adds coin to all coin boxes from to (inclusive).
The next line contains an integer (1 \le q \le 10^6), the number of queries.
Each of the next lines contains a single integer (1 \le x \le n), describing a query.
For each query, output the answer in a separate line.
Shembulli 1