# Roy and Coin Boxes

Medium

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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â‰¤10_{6})$. Second line contains number of days $mÂ(1â‰¤mâ‰¤10_{6})$. 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â‰¤10_{6})$. Each of next $q$ lines contain a single integer $xÂ(1â‰¤xâ‰¤n)$.

## Output

For each query output the result in a new line.

## Examples

Input #1

Answer #1

Submissions 1K

Acceptance rate 37%