2022 年上海市大学生程序设计竞赛 - 十月赛

B. 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


NaN