# 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%