题目描述

题目译自 Open Olympiad in Informatics 2018 Day2 T1 「Чехарда в массиве / A Leapfrog in the Array」。

迪玛是一位初级程序员。在工作中，他经常需要执行一个相同的操作：从数组中删除每隔一个元素。有一天，他厌倦了这种简单的解决方案，于是想出了一个独特的算法。

假设初始时数组中有 $n$ 个数字，值从 $1$ 到 $n$，其中数字 $i$ 位于编号为 $2i - 1$ 的单元格中（数组元素的编号从 $1$ 开始），而数组的其他单元格为空。接下来，在每一步中，迪玛选择一个非空的、编号最大的单元格，并将其中记录的数字移动到左侧最近的空单元格。这个过程持续进行，直到所有 $n$ 个数字都位于数组的前 $n$ 个单元格中。例如，当 $n = 4$ 时，数组内容的变化如下：

你需要编写一个程序，确定在迪玛的算法结束后，编号为 $x$ $(1 \leq x \leq n)$ 的单元格中最终会是哪个数字。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 10^{18}, 1 \leq q \leq 200000)$，分别表示数组中的元素数量和需要回答的查询数量。

接下来的 $q$ 行，每行包含一个整数 $x_i$ $(1 \leq x_i \leq n)$，表示需要确定算法结束后内容所在的单元格编号。

输出格式

对于 $q$ 个查询中的每个查询，输出一个整数，即迪玛的算法结束后指定单元格中的值。

4 3
2
3
4

3
2
4

在样例中，$n = 4$，有 $3$ 个查询：

• 查询 $2$：算法结束后，单元格 $2$ 中的值为 $3$。
• 查询 $3$：算法结束后，单元格 $3$ 中的值为 $2$。
• 查询 $4$：算法结束后，单元格 $4$ 中的值为 $4$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。