G. Daggers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a videogame. In this game, there's an assassin throwing daggers at you, one dagger is thrown every $$$t$$$ seconds and the dagger doesn't take any time to arrive to its destination. You are running through the $$$x$$$-axis of the Euclidean Plane at a constant speed of $$$1$$$ unit per second, and you can decide to stop at any point for some number of seconds. Your goal is to arrive to the coordinate $$$n$$$ in the $$$x$$$-axis without being killed by the assassin.

The game consists of $$$q$$$ levels, each numbered from $$$1$$$ to $$$q$$$, and each level will add one more shield that will be present on this and the next levels. You are safe from a dagger if you are at a shield or at the end point when the dagger is thrown. If not, you will lose. Shields don't vanish when they protect you from a dagger, so you can use the same shield multiple times. Additionally, for each level, $$$t$$$ is equal to the number of that level (for level $$$1$$$, $$$t$$$ will be equal to $$$1$$$; for level $$$2$$$, $$$t$$$ will be equal to $$$2$$$; and so on). Note that this game is a bit weird, so you will always pass to the next level and start again from coordinate $$$0$$$, regardless of whether you have managed to arrive to the coordinate $$$n$$$ or not.

You want to boost your performance so you have decided to calculate if you will be able to pass each level and, if it's possible to do so, the least number of seconds you need to do it.

Input

The first line will consist of two integers, $$$n$$$ and $$$q(2 \leq n \leq 2 \cdot 10^{5}; 1 \leq q \lt n).$$$

Each of the next $$$q$$$ lines will contain one integer $$$x$$$, denoting the coordinate of the new shield. $$$(1 \leq x \lt n).$$$

It is guaranteed that at all times there is at most one shield at any coordinate.

$$$-$$$

Testcases in the subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

For testcases $$$1-13$$$, $$$2 \le n \le 2000$$$ and $$$1 \le q \le 2000$$$.

The remaining testcases do not satisfy any additional constraints.

Output

You must output $$$q$$$ lines. On the $$$i$$$-th line, you must output $$$-1$$$ if it is impossible to arrive to the coordinate $$$n$$$ in the level $$$i$$$. Otherwise, you must output an integer $$$s$$$, the minimum number of seconds to pass the level $$$i$$$.

Examples
Input
7 4
1
2
3
4
Output
-1
-1
-1
7
Input
10 6
2
5
9
1
3
6
Output
-1
-1
-1
13
10
10
Note

In the first sample, there is no way to arrive to coordinate $$$7$$$ in the first three levels. In the fourth level, you could stop at the shield in position $$$4$$$ just in time, when the dagger is thrown, and then arrive at coordinate $$$7$$$.

In the second sample, there is no way to arrive to coordinate $$$10$$$ in the first three levels. For level $$$4$$$, you could go to shields at positions $$$1$$$, $$$5$$$, $$$9$$$ until a dagger was thrown and then arrive to $$$10$$$. For the next levels, you can stay at position $$$5$$$ until the first dagger is thrown and then go to $$$10.$$$

$$$-$$$

Idea: Esomer

Preparation: Esomer

Ocurrences: Novice 7, Advanced 3