Roy has coin boxes numbered from to . Every day he selects two indices and adds coin to each coin box starting from to (both inclusive). He does this for number of days.
After days, Roy has a query: How many coin boxes have at least coins. He has such queries.
First line contains number of coin boxes . Second line contains number of days . Each of the next lines consists of two space separated integers and . Followed number is the number of queries . Each of next lines contain a single integer .
For each query output the result in a new line.