How to approach this ?

Question
Asha has got a set of integers and he is thinking about what interesting problem statement could be formed from these integers. And Eureka! She found one!

The problem statement goes as follow:

  1. You have to find the maximum integer among the set of integers and divide the integer by 2.
  2. Since this is an integer division the result of division will be an integer.
  3. After division if the integer is greater than 0, then we put the updated integer again in the set of integers.

Asha gives you m queries, each query q[i] means, that q[q[i]āˆ’1] number of operations has already been performed, and its time to perform q[i]th operation. Your task is to tell that for q[i]th operation which integer will get divided.

Input Format

The first line contains 2 space-separated integers n,m
denoting the number of integers and the number of queries respectively.
The next line contains n space-separated integers followed by m lines.
In the next m lines, the ith line will contain q[i].

Output format

Output m lines, the ith of which contains the answer for the ith query.

Constraints

1<=n,m<=10^6
1<=n,m<=10^6

For 1<=i<=m1<=i<=m,
q[i]>q[iāˆ’1].

For 0<=i<=n0<=i<=n,
1<=a[i]<=1091<=a[i]<=109

If no integer is present at the time of the query stop the program.

Example

Input

4 6
8 5 3 1
1
2
3
4
6
8

Output

8
5
4
3
2
1