Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

B. Чехарда в массиве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дима — начинающий программист. В ходе работы ему регулярно приходится проделывать одну и ту же операцию: удалить из массива каждый второй элемент. В один прекрасный день ему надоели простые решения этой задачи, и он придумал следующий экстравагантный алгоритм.

Будем считать, что изначально в массиве находятся n чисел от 1 до n, причём число i располагается в ячейке c индексом 2i - 1 (нумерация элементов в массиве начинается с единицы), а остальные ячейки массива пустые. Далее, на каждом шаге Дима выбирает непустую ячейку массива с максимальным индексом, и перемещает записанное в ней число в ближайшую пустую ячейку слева от выбранной. Процесс продолжается до тех пор, пока все n чисел не окажутся в первых n ячейках массива. Например, если n = 4, содержимое массива изменяется следующим образом:

Вам предстоит написать программу, которая позволит определять, какое число окажется в ячейке под номером x (1 ≤ x ≤ n) после окончания работы алгоритма Димы.

Входные данные

В первой строке вводятся целые числа n и q (1 ≤ n ≤ 1018, 1 ≤ q ≤ 200 000) — число элементов в массиве и количество запросов, на которые необходимо дать ответ. В каждой из последующих q строк вводится целое число xi (1 ≤ xi ≤ n) — номер ячейки, для которой необходимо определить содержимое после окончания работы алгоритма.

Выходные данные

Для каждого из q запросов выведите одно целое число — значение, которое будет содержать указанная ячейка массива после окончания работы алгоритма Димы.

Примеры
Входные данные
4 3
2
3
4
Выходные данные
3
2
4
Входные данные
13 4
10
5
4
8
Выходные данные
13
3
8
9
Примечание

Первый пример показан на рисунке.

Во втором примере окончательный массив выглядит так: [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].