C. Meta Frequency
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Stanford's football team is doing end-of-year performance reviews. Coach Sao is very upset with his team members for being late to practice! There are $$$S$$$ players on the team, numbered $$$1$$$ to $$$S$$$, and every time a player is late, he writes their number on the whiteboard. Looking at the whiteboard, they have been late $$$N$$$ times in total.

Coach Sao has decided to make the players do push-ups as punishment. Player $$$k$$$ has to count how many total times the players numbered $$$1$$$ to $$$k$$$ have been late, and then do that number of push-ups. MTL is wondering whether Coach Sao is too cruel to his players, so he asks him, "How many players do at most $$$x$$$ push-ups?" MTL is very forgetful, so he may ask Coach Sao up to $$$Q$$$ questions. He may ask multiple questions with the same $$$x$$$. Since $$$Q$$$ and $$$x$$$ may be large, help Coach Sao answer these questions!

Input

The first line contains two space separated integers, $$$S$$$ and $$$N$$$ ($$$1 \leq S \leq 10^9$$$, $$$1\leq N \leq 10^5$$$).

The second line contains $$$N$$$ space-separated integers: the numbers on the whiteboard.

The third line contains an integer $$$Q$$$, ($$$1 \leq Q \leq 10^5$$$) the number of questions MTL will ask.

The next $$$Q$$$ lines represent the questions. Each question will be the integer $$$x$$$, ($$$0 \leq x \leq 10^9$$$) on one line.

Output

For every question, output the answer in one line.

Example
Input
4 6
1 2 4 2 2 1
2
1
3
Output
0
1