幻兽帕鲁
题号：NC272821
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在幻兽帕鲁中，不同的帕鲁能干不同的工作，现在我们要对帕鲁进行分类以便他们能够更好的进行压榨。

你有 2^n 只帕鲁，初始给每只帕鲁一个工号，并让帕鲁按 [0,2^n-1] 工号的顺序排成一队。

当我们对区间 [l,r] 的帕鲁进行操作时，我们会对该区间的帕鲁按顺序进行临时编号 [0,r-l] ，记 mid = \lfloor\frac{l + r}{2}\rfloor，我们将临时编号为偶数和奇数的帕鲁，分别按顺序置于区间 [l,mid] 和 [mid + 1,r] ，并递归对这两个区间进行上述操作，直到区间长度为 1 。

现在我们对 [0,2^n-1] 的幻兽进行一次操作，然后给你 m 次询问，每次询问 x 位置的帕鲁工号是多少？

输入描述:

第一行两个整数 n, m(0 \leq n \leq 60, 1\leq m\leq 10^5) 。

接下来 m 行，每行一个整数 x 表示询问第 x 个位置的帕鲁的工号，位置从 0 开始计数。

输出描述:

输出每次询问的帕鲁的工号。
示例1

输入

复制 
2 4
0
1
2
3

输出

复制 
0
2
1
3
示例2

输入

复制 
3 4
0
2
5
7

输出

复制 
0
2
5
7