# 4900. Questions on Binary Tree

Given is a rooted tree with $n$ nodes. And for convenience，we set node $1$ as its root.

Moreover, the parent of the $i$-th node is $\lfloor \frac{i}{2} \rfloor$, where $2\le i\le n$.

Apparently, this is a binary tree, and for the $i$-th node, its left child is $2i$ and its right child is $2i+1$ (If it has the corresponding child).

Now, here come $m$ questions. The $i$-th question will ask you the rank of the $x_i$-th node in the preorder traversal of the tree.

As a promissing programmer, you’re not throwing away your shot. So you need to give the answer of every question.

Preorder Traversal

Algorithm Preorder(tree)
Visit the root.
Traverse the left subtree, i.e., call Preorder(tree->left)
Traverse the right subtree, i.e., call Preorder(tree->right)


For example, when $n=10$, the preorder of the tree is ${1,2,4,8,9,5,10,3,6,7}$.

### 输入格式

The first line contains $2$ integers $n,m\ (1\le n\le 10^{18},\ 1\le m\le 10^5)$, denoting the number of the nodes in this tree and the number of the questions, respectively.

Next $m$ lines, for $i$-th line, contains an integer $x_i\ (1\le x_i\le n)$ , denoting a question about the rank of node $x_i$ in the preorder of the tree.

### 样例

Input
10 5
1
3
5
7
9

Output
1
8
6
10
5


162 人解决，222 人已尝试。

175 份提交通过，共有 861 份提交。

3.5 EMB 奖励。