У Кати есть веревочка длиной \(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
|
100
5
6
1 2 3 4 5 6
|
25 25 13 13 12 12
|