Description

In the year of $114514$, the annual UESTC Fun Programming Contest is about to kick off. As the number of participants is increasing explosively, for example, last year, $1919810$ students signed up for the competition. In order to make the competition more exciting, the Organizing Committee decides to change the competition system to the elimination competition.

The rules of the elimination competition are as follows: Suppose there are $2^n$ contestants, arranged in the order from $1$ to $2^n$, and the relative position of the contestants will not change during the competition. There are a total of $n$ rounds in the competition. At the first round, contestants numbered $2i-1$ and contestants numbered $2i$ will solve a problem by programming within a limited time. The contestants who pass with less time will be promoted. The contestants who do not advance will be eliminated directly, and there will be no tie. At the second round, two contestants numbered from $4i-3$ to $4i$ who won the last round will continue to compete under the same rules... At the $j$-th round, two contestants numbered from $(i-1)2^j+1$ to $i2^j$ will compete until there is only one contestant left, who is the champion of the whole competition and will win the prize of unique sleeping black tea!

Now, the committee has entrusted Bob with the task of arranging the number of contestants. However, Bob is busy eating snow, so he gives this tough task to you and explains the conditions of the contestants. First of all, to ensure that the competition can continue, the number of participants must be $2^n$; secondly, each contestant will have an ability value between $1$ and $2^n$. And the ability values between any two contestants are different. All the contestants can solve all the questions. The faster the contestants with higher ability value can solve the questions. For example, the contestants with the ability value of $2$ and the ability value of $3$ have both worked out a question, but the contestant with the ability value of $3$ can work faster, so the contestant with the ability value of $3$ is promoted, and the contestant with the ability value of $2$ is eliminated.

But Bob has a good friend. He hopes you can plan a way to arrange the number of contestants so that this friend can promote as many times as possible.

Input

The first line contains two integers $n,m$ ($0\leq n< 63,1\leq m\leq 2\times 10^5$), representing the number of contestants is $2^n$ and the number of inquiries.

For the next $m$ lines, each line contains an integer $x_i$ ($1\leq x_i\leq 2^n$), indicating that Bob wants the contestant whose capability value is $x_i$ to be promoted as many times as possible. All queries are independent with each other, which means that you can rearrange the number of contestants for each query, and you only need to ensure that in the current query the contestant whose capability value is $x_i$ be promoted as many times as possible without considering other contestants.

Output

A total of $m$ lines, for each line with an integer $y_i$, which means the contestant whose capability value is $x_i$ can be promoted at most $y_i$ times. You do not need to output the concrete arrangement.

Samples

3 3
1
5
8

0
2
3

Note

For question $1$, no matter how to arrange the number, the contestant with the ability value of $1$ must be eliminated in the first round, so the number of promotions is $0$;

For question $2$, one arrangement is $6, 8, 7, 3, 2, 4, 5, 1$. The flow chart of the competition can be made as follows:

Therefore, the promotion times are $2$;

For question $3$, no matter how to arrange the number, the contestant with the ability value of $8$ must be the champion of this competition. The number of promotions is $3$, and this person will win the prize of unique sleeping black tea.

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛