Dima 是一名初级程序员。在他的工作过程中,他经常需要一次又一次地重复以下操作:从数组中删除每一个元素。有一天,他厌倦了这个问题的简单解决方案,他想出了以下奢侈的算法。
让我们考虑最初数组包含从 1 到 n 的 n 个数字,并且数字 i 位于索引为 2i - 1 的单元格中(索引从 1 开始编号),数组的其他单元格为空。每一步 Dima 都会选择一个具有最大索引的非空数组单元格,并将其中写入的数字移动到所选单元格左侧最近的空单元格。该过程继续进行,直到所有 n 个数字都出现在数组的前 n 个单元格中。例如,如果 n = 4,则数组将按如下方式更改:
您必须编写一个程序,允许您确定 Dima 算法完成后索引为 x (1 ≤ x ≤ n) 的单元格中将包含什么数字。
输入
第一行包含两个整数 n 和 q (1 ≤ n ≤ 1018, 1 ≤ q ≤ 200 000)、数组中的元素数量以及查找答案所需的查询数量。
接下来的 q 行包含整数 xi (1 ≤ xi ≤ n),即在 Dima 算法完成后需要输出其内容的单元格索引。
输出
对于 q 个查询中的每一个输出一个整数,该值将在 Dima 算法完成后出现在相应的数组单元中。
示例
输入 #1
4 3 2 3 4
输出 #1
3 2 4
输入 #2
13 4 10 5 4 8
输出 #2
13 3 8 9
注意
第一个示例如图所示。
在第二个示例中,最终数组是 [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7]。