В турнире участвуют $$$2^N$$$ команд. Турнир длится $$$K$$$ раундов.
Перед первым раундом команды стоят в таблице в произвольном порядке. В каждом раунде команды разбиваются на пары по текущей таблице: $$$1$$$-я команда играет со $$$2$$$-й, $$$3$$$-я — с $$$4$$$-й, и так далее. В каждой паре одна команда побеждает, а другая проигрывает — ничьих не бывает.
После каждого раунда таблица пересортировывается по следующим правилам:
Статистикой команды назовём двоичную строку $$$b_1 b_2 \ldots b_K$$$, где $$$b_i = 1$$$, если команда победила в $$$i$$$-м раунде, и $$$b_i = 0$$$, если проиграла. Статистику будем записывать одним числом $$$\sum\limits_{i=1}^{K} b_i \cdot 2^{i-1}$$$: результат первого раунда — младший бит, результат последнего — старший.
Команды между собой не различаются, а исходы матчей неизвестны. Можно показать, что от исходов матчей зависит лишь то, какая именно команда окажется на той или иной позиции итоговой таблицы, но не статистика команды на этой позиции.
Вам даны $$$Q$$$ запросов: для каждой позиции $$$P_i$$$ определите статистику команды, которая окажется на этой позиции после $$$K$$$ раундов.
В первой строке через пробел содержатся три целых числа $$$N$$$, $$$K$$$, $$$Q$$$ $$$(1 \le K \le N \le 30;\ 1 \le Q \le 10^5)$$$ — логарифм количества команд (всего команд $$$2^N$$$), количество раундов и количество запросов.
Во второй строке через пробел содержатся $$$Q$$$ целых чисел $$$P_1, P_2, \ldots, P_Q$$$ $$$(1 \le P_i \le 2^N)$$$ — позиции в итоговой таблице после $$$K$$$ раундов. Позиции нумеруются от $$$1$$$ до $$$2^N$$$ сверху вниз.
Выведите в одной строке через пробел $$$Q$$$ целых чисел $$$S_1, \ldots, S_Q$$$. Число $$$S_i$$$ $$$(0 \le S_i \lt 2^K)$$$ — статистика команды, стоящей на позиции $$$P_i$$$ итоговой таблицы, записанную числом: $$$S_i = \sum\limits_{j=1}^{K} b_j \cdot 2^{j-1}$$$, где $$$b_j = 1$$$, если команда победила в $$$j$$$-м раунде, и $$$b_j = 0$$$ в противном случае.
2 2 41 2 3 4
3 2 1 0
3 3 88 7 6 5 4 3 2 1
0 1 2 4 3 5 6 7
4 2 51 4 5 12 16
3 3 2 1 0
Пример 1. Рассмотрим один из возможных исходов турнира для команд $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$. В раунде $$$1$$$ команда $$$A$$$ побеждает $$$B$$$, команда $$$C$$$ побеждает $$$D$$$; таблица становится $$$A, C, B, D$$$ (у $$$A$$$ и $$$C$$$ по одной победе). В раунде $$$2$$$ команда $$$A$$$ побеждает $$$C$$$, команда $$$B$$$ побеждает $$$D$$$; статистики команд: $$$A = 11$$$, $$$C = 10$$$, $$$B = 01$$$, $$$D = 00$$$. Итоговая таблица: сначала $$$A$$$ (две победы), затем среди команд с одной победой выше $$$B$$$, выигравшая последнюю встречу, затем $$$C$$$, затем $$$D$$$. Статистики на позициях $$$1, 2, 3, 4$$$: $$$11, 01, 10, 00$$$, то есть числа $$$1 + 2 = 3$$$, $$$2$$$, $$$1$$$, $$$0$$$ (первый символ — младший бит).
При другом исходе — $$$B$$$ побеждает $$$A$$$, $$$D$$$ побеждает $$$C$$$ в раунде $$$1$$$, затем $$$D$$$ побеждает $$$B$$$, $$$A$$$ побеждает $$$C$$$ в раунде $$$2$$$ — на позициях $$$1, 2, 3, 4$$$ окажутся команды $$$D, A, B, C$$$ со статистиками $$$11, 01, 10, 00$$$: команды на позициях другие, а статистики те же.
Пример 2. При $$$K = 3$$$ статистики в итоговой таблице (от позиции $$$1$$$ до позиции $$$8$$$) идут в порядке $$$111, 011, 101, 110, 001, 010, 100, 000$$$, то есть $$$7, 6, 5, 3, 4, 2, 1, 0$$$. Например, $$$011$$$ и $$$101$$$ обе выиграли последний (третий) раунд, поэтому сравнивается предпоследний: у $$$011$$$ там победа, у $$$101$$$ — поражение, значит $$$011$$$ выше. Статистика $$$110$$$ проиграла последний раунд и стоит ниже обеих, несмотря на равное число побед. Запросы даны в порядке $$$8, 7, \ldots, 1$$$, и ответы выводятся в том же порядке.
Пример 3. При $$$N = 4$$$, $$$K = 2$$$ команд $$$16$$$, а различных статистик — $$$4$$$. Каждая встречается ровно у $$$4$$$ команд подряд: позиции $$$1$$$–$$$4$$$ — статистика $$$11$$$ (число $$$3$$$), $$$5$$$–$$$8$$$ — $$$01$$$ ($$$2$$$), $$$9$$$–$$$12$$$ — $$$10$$$ ($$$1$$$), $$$13$$$–$$$16$$$ — $$$00$$$ ($$$0$$$).
