Веревочки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кати есть веревочка длиной $$$n$$$ сантиметров.

Катя $$$k$$$ раз выполняет следующую операцию: выбирает самую длинную веревочку из тех, что у неё есть, и разрезает ее на две веревочки. Катя каждый раз разрезает веревочку на две веревочки примерно равной длины, длина каждой из получившихся веревочек измеряется целым числом сантиметров. А именно: если длина веревочки, которую разрезает Катя, четная и равна $$$2u$$$, то после разрезания получается две веревочки длины $$$u$$$, а если она нечетная и равна $$$2v+1$$$, то после разрезания получаются веревочки длиной $$$v$$$ и $$$v+1$$$.

Когда Катя закончила разрезать веревочку, она разложила получившиеся веревочки в порядке невозрастания длины и хочет ответить на $$$q$$$ запросов: какая длина $$$t_i$$$-й веревочки в получившемся порядке.

Например, пусть $$$n=100$$$ и $$$k=5$$$. Тогда у Кати последовательно есть наборы веревочек следующей длины: $$$[100]$$$, $$$[50, 50]$$$, $$$[50, 25, 25]$$$, $$$[25, 25, 25, 25]$$$, $$$[25, 25, 25, 13, 12]$$$, $$$[25, 25, 13, 13, 12, 12]$$$.

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

На первой строке ввода дано целое число $$$n$$$ ($$$2 \le n \le 10^{18}$$$).

На второй строке дано целое число $$$k$$$ ($$$1 \le k \le n-1$$$).

На третьей строке дано целое число $$$q$$$ ($$$1 \le q \le k + 1$$$, $$$1 \le q \le 5000$$$).

На четвертой строке даны $$$q$$$ целых чисел $$$t_1, t_2, \ldots, t_q$$$ ($$$1 \le t_1 < t_2 < \ldots < t_q \le k + 1$$$).

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

Выведите $$$q$$$ чисел, $$$i$$$-е из выведенных чисел должно быть равно длине $$$t_i$$$-й по невозрастанию длине веревочки, которая в итоге есть у Кати.

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

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

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
113$$$n \le 5000$$$, $$$k = n - 1$$$, $$$q = k + 1$$$ 
215$$$n \le 5000$$$, $$$q = k + 1$$$1
319$$$k \le 5000$$$1, 2
419$$$k \le 10^5$$$1–3
5341–4

Пример

Входные данные
100
5
6
1 2 3 4 5 6
Выходные данные
25 25 13 13 12 12