4900. Questions on Binary Tree

单点时限: 1.0 sec

内存限制: 256 MB

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.

输出格式

For each question , output an integer, which represents your answer.

样例

Input
10 5
1
3
5
7
9
Output
1
8
6
10
5

161 人解决,218 人已尝试。

174 份提交通过,共有 850 份提交。

3.4 EMB 奖励。

创建: 1 月,1 周前.

修改: 1 月,1 周前.

最后提交: 5 天,19 小时前.

来源: N/A

题目标签