У Кати есть веревочка длиной $$$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$$$-й по невозрастанию длине веревочки, которая в итоге есть у Кати.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
1 | 13 | $$$n \le 5000$$$, $$$k = n - 1$$$, $$$q = k + 1$$$ | |
2 | 15 | $$$n \le 5000$$$, $$$q = k + 1$$$ | 1 |
3 | 19 | $$$k \le 5000$$$ | 1, 2 |
4 | 19 | $$$k \le 10^5$$$ | 1–3 |
5 | 34 | — | 1–4 |
100561 2 3 4 5 6
25 25 13 13 12 12