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 data

First line contains number of coin boxes n~(1 \le n \le 10^6). Second line contains number of days m~(1 \le m \le 10^6). Each of the next m lines consists of two space separated integers l and r~(1 \le l \le r \le n). Followed number is the number of queries q~(1 \le q \le 10^6). Each of next q lines contain a single integer x~(1 \le x \le n).

## Output data

For each query output the result in a new line.

## Examples

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