Statement is not available in English language
D. Шторы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда кот Бенедикт был котёнком, он с удовольствием взбирался по шторам на гардину и гулял по ней. Собственно, он и сейчас не прочь пройтись по гардине, но предпочитает перебираться на неё со шкафа, поскольку путь по шторам по ряду причин не представляется ему безопасным. К тому же не так давно его хозяйка решила поменять шторы. Бенедикт с интересом наблюдал за процессом развешивания штор.

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

Сначала она закрепляет штору на крючках с номерами $$$1$$$ и $$$n$$$ (можете считать, что это происходит одновременно). После этого она каждый раз выбирает наиболее длинный отрезок из неиспользованных крючков и закрепляет штору в середине этого отрезка. Опишем процесс более формально.

Пусть на некотором шаге имеется некоторое количество $$$k$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$, где $$$l_j$$$ и $$$r_j$$$ — номера крючков, $$$1 \lt l_1 \le r_1 \lt l_2 \le r_2 \lt \ldots \lt l_k \le r_k \lt n$$$. Для каждого такого отрезка верно, что ни на одном крючке, начиная с $$$l_j$$$ и заканчивая $$$r_j$$$, штора ещё не закреплена.

Хозяйка Бенедикта выберет тот отрезок, для которого $$$r_j - l_j$$$ максимально; если же таких отрезков несколько, выберет самый левый из них (с наименьшим $$$j$$$). Количество свободных крючков на отрезке $$$[l_j, r_j]$$$ равно $$$r_j - l_j + 1$$$. Если это количество нечётное, хозяйка Бенедикта закрепляет штору на среднем крючке (его номер $$$l_j + (r_j - l_j)/2$$$). Если же количество крючков чётное, хозяйка Бенедикта закрепляет штору на двух средних крючках (с номерами $$$l_j + (r_j - l_j - 1)/2$$$ и $$$l_j + (r_j - l_j +1)/2$$$).

Ваша задача — по заданным номерам крючков определить, на каком шаге на каждом из них была закреплена штора.

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

В первой строке содержатся целые числа $$$n$$$ и $$$q$$$ $$$(1 \le n \le 10^{18}, \, 1 \le q \le 10^3)$$$ — количество крючков, на которых держится штора, и количество крючков, для которых нужно определить номер шага, на котором они были использованы для закрепления шторы..

Во второй строке содержатся $$$q$$$ целых чисел $$$a_1, a_2, \dots, a_q$$$ $$$(1 \le a_i \le n)$$$ — номера крючков, для каждого из которых необходимо определить номер шага, на котором на этом крючке была закреплена штора. Гарантируется, что все номера попарно различны, иными словами $$$a_i \not= a_k$$$ для $$$i \not= k$$$.

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

В единственной строке через пробел выведите $$$q$$$ чисел $$$t_i$$$, где $$$t_i$$$ — номер шага, на котором крючок $$$a_i$$$ был использован для закрепления шторы.

Система оценки

В первых трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

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

Также для некоторых подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 10)$$$n \le 10$$$, $$$q = n$$$нетполная
23 (до 15)$$$n \le 10^3$$$,1полная
33 (до 15)$$$n \le 3 \cdot 10^5$$$,1, 2полная
40 (20)Ответы $$$t_i \le 3 \cdot 10^5$$$1, 2, 3первая ошибка
50 (15)$$$n = 2^k$$$ для $$$k$$$ > $$$0$$$нетпервая ошибка
60 (25)любые допустимые значения1, 2, 3, 4, 5первая ошибка

Примеры
Входные данные
10 10
1 10 2 9 3 8 4 7 5 6
Выходные данные
1 1 5 8 3 4 6 7 2 2
Входные данные
9876543210 3
3456789120 5678912340 7891234560
Выходные данные
5798205414 6764530002 3863296238
Примечание

Первый тестовый пример.

Штора держится на $$$n = 10$$$ крючках.

Крючки будут использованы в следующем порядке:

  1. На первом шаге закрепляем штору на крайних крючках с номерами $$$1$$$ и $$$10$$$;
  2. На втором шаге имеется один отрезок крючков $$$[2, 9]$$$, состоящий из $$$8$$$ крючков. Поэтому закрепляем штору на центральных крючках $$$5 = 2 + (9 - 2 - 1) / 2$$$ и $$$6 = 2 + (9 - 2 + 1) / 2$$$;
  3. На третьем шаге рассматриваем два отрезка $$$[2, 4]$$$ и $$$[7, 9]$$$. Они имеют одинаковую длину $$$3$$$, поэтому выбираем отрезок $$$[2, 4]$$$ как самый левый и закрепляем штору на среднем крючке этого отрезка — на крючке с номером $$$3$$$.
  4. На четвертом шаге рассматриваем три отрезка $$$[2, 2]$$$, $$$[4, 4]$$$ и $$$[7, 9]$$$. Наибольшую длину среди них имеет отрезок $$$[7, 9]$$$, поэтому закрепляем штору на среднем крючке этого отрезка — на крючке с номером $$$8$$$ $$$(8 = 7 + (9 - 7)/2)$$$.
  5. Остались только отрезки, состоящие из одного крючка каждый $$$[2, 2]$$$, $$$[4, 4]$$$, $$$[7, 7]$$$ и $$$[9, 9]$$$. Поэтому на каждом из следующих четырёх шагов выбираем самый левый из таких отрезков и закрепляем штору на нём. Таким образом, на пятом шаге штора будет закреплена на крючке $$$2$$$;
  6. На шестом шаге закрепляем штору на самом левом из оставшихся крючков — крючке с номером $$$4$$$;
  7. На седьмом шаге закрепляем штору на крючке с номером $$$7$$$;
  8. Наконец, на восьмом шаге закрепляем штору на крючке с номером $$$9$$$. Штора закреплена полностью.

Теперь остаётся только записать в ответ соответствующие номера шагов.