H. Speedway Evacuation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ students standing on Speedway, each at some position between $$$1$$$ to $$$n-1$$$. Each student randomly faces either left (towards position $$$0$$$) or right (towards position $$$n$$$) with equal probability independent of any other students. At time $$$t=0$$$, each student begins to move one position per second in the direction they are facing.

If two students collide, they switch directions without stopping. Two students may start at the same location; if they move in the same direction they never collide.

Given $$$q$$$ queries $$$t$$$, each asking for the probability that no students have exited Speedway (i.e., reached position $$$0$$$ or $$$n$$$) after $$$t$$$ seconds, determine the result for each query. It can be shown the probability that no students have exited Speedway is either 0 or of the form $$$2^{-m}$$$ for some integer $$$m$$$. You should output $$$m$$$ for each query. If the probability is $$$0$$$, output $$$-1$$$ instead.

Input

The first line contains two integers $$$n$$$ and $$$q\ (2 \leq n \leq 10^5, 1 \leq q \leq 10^5)$$$, the length of Speedway and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2,...,a_n\ (1\leq a_i\leq n-1)$$$ representing the initial positions of the students, not necessarily sorted.

The next q lines each contain an integer $$$t\ (1 \leq t \leq 10^8)$$$ representing a query, where $$$t$$$ is the time (in seconds) after which you need to determine the probability that no students have evacuated Speedway.

Output

It can be shown the probability that no students have exited Speedway is either 0 or of the form $$$2^{-m}$$$. You should output $$$m$$$ for each query, one on each line. If the probability is $$$0$$$, output $$$-1$$$ instead.

Example
Input
7 2
6 6 2 2 2 3 3
1
100
Output
2
-1
Note

After $$$1$$$ second, no students have exited Speedway as long as the two students at location $$$6$$$ are both facing left, which has probability $$$\frac{1}{4} = 2^{-2}$$$. After $$$100$$$ seconds, it would be impossible for no students to have exited.