G. Are ya winning, son?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The tournament features $$$2^N$$$ teams. The tournament lasts for $$$K$$$ rounds.

Before the first round, the teams are placed in the table in an arbitrary order. In each round, the teams are split into pairs according to the current table: the $$$1$$$-st team plays the $$$2$$$-nd, the $$$3$$$-rd — the $$$4$$$-th, and so on. In each pair, one team wins and the other loses — there are no draws.

After each round, the table is resorted according to the following rules:

  • a team with more wins is placed higher;
  • if the number of wins is the same, the team that won the last played match is placed higher;
  • if that is also the same — the results of the second-to-last match are compared, and so on, all the way back to the first round.

We define a team's statistics as the binary string $$$b_1 b_2 \ldots b_K$$$, where $$$b_i = 1$$$ if the team won in the $$$i$$$-th round, and $$$b_i = 0$$$ otherwise. We will encode the statistics as the number $$$\sum\limits_{i=1}^{K} b_i \cdot 2^{i-1}$$$: the result of the first round is the least significant bit, and the result of the last round is the most significant bit.

The teams are indistinguishable from one another, and the outcomes of the matches are unknown. It can be shown that the outcomes of the matches affect only which exact team ends up in a given position of the final table, but not the statistics of the team in that position.

You are given $$$Q$$$ queries: for each position $$$P_i$$$, determine the statistics of the team that ends up in that position after $$$K$$$ rounds.

Input

The first line contains three integers $$$N$$$, $$$K$$$, $$$Q$$$ $$$(1 \le K \le N \le 30;\ 1 \le Q \le 10^5)$$$ separated by spaces — the logarithm of the number of teams (there are $$$2^N$$$ teams in total), the number of rounds, and the number of queries.

The second line contains $$$Q$$$ integers $$$P_1, P_2, \ldots, P_Q$$$ $$$(1 \le P_i \le 2^N)$$$ separated by spaces — positions in the final table after $$$K$$$ rounds. Positions are numbered from $$$1$$$ to $$$2^N$$$ from top to bottom.

Output

Print $$$Q$$$ integers $$$S_1, \ldots, S_Q$$$ in one line separated by spaces. The number $$$S_i$$$ $$$(0 \le S_i \lt 2^K)$$$ is the statistics of the team standing at position $$$P_i$$$ in the final table, encoded as a number: $$$S_i = \sum\limits_{j=1}^{K} b_j \cdot 2^{j-1}$$$, where $$$b_j = 1$$$ if the team won in the $$$j$$$-th round, and $$$b_j = 0$$$ otherwise.

Examples
Input
2 2 4
1 2 3 4
Output
3 2 1 0
Input
3 3 8
8 7 6 5 4 3 2 1
Output
0 1 2 4 3 5 6 7
Input
4 2 5
1 4 5 12 16
Output
3 3 2 1 0
Note

Example 1. Consider one possible outcome of the tournament for teams $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$. In round $$$1$$$, team $$$A$$$ beats $$$B$$$, and team $$$C$$$ beats $$$D$$$; the table becomes $$$A, C, B, D$$$ (teams $$$A$$$ and $$$C$$$ each have one win). In round $$$2$$$, team $$$A$$$ beats $$$C$$$, and team $$$B$$$ beats $$$D$$$; the teams' statistics are: $$$A = 11$$$, $$$C = 10$$$, $$$B = 01$$$, $$$D = 00$$$. The final table is: first $$$A$$$ (two wins), then among the teams with one win, $$$B$$$ is higher because it won the last match, then $$$C$$$, then $$$D$$$. The statistics at positions $$$1, 2, 3, 4$$$ are $$$11, 01, 10, 00$$$, that is, the numbers $$$1 + 2 = 3$$$, $$$2$$$, $$$1$$$, $$$0$$$ (the first digit is the least significant bit).

For another outcome — $$$B$$$ beats $$$A$$$, $$$D$$$ beats $$$C$$$ in round $$$1$$$, then $$$D$$$ beats $$$B$$$, $$$A$$$ beats $$$C$$$ in round $$$2$$$ — the teams at positions $$$1, 2, 3, 4$$$ are $$$D, A, B, C$$$ with statistics $$$11, 01, 10, 00$$$: the teams in the positions are different, but the statistics are the same.

Example 2. For $$$K = 3$$$, the statistics in the final table (from position $$$1$$$ to $$$8$$$) are ordered as $$$111, 011, 101, 110, 001, 010, 100, 000$$$, that is, $$$7, 6, 5, 3, 4, 2, 1, 0$$$. For example, both $$$011$$$ and $$$101$$$ won the last (third) round, so the second-to-last round is compared: $$$011$$$ has a win there, while $$$101$$$ has a loss, so $$$011$$$ is higher. The statistic $$$110$$$ lost the last round and is below both of them, despite having the same number of wins. The queries are given in the order $$$8, 7, \ldots, 1$$$, and the answers are printed in the same order.

Example 3. For $$$N = 4$$$, $$$K = 2$$$, there are $$$16$$$ teams, and there are $$$4$$$ different statistics. Each appears for exactly $$$4$$$ consecutive teams: positions $$$1$$$–$$$4$$$ correspond to statistic $$$11$$$ (number $$$3$$$), $$$5$$$–$$$8$$$ to $$$01$$$ ($$$2$$$), $$$9$$$–$$$12$$$ to $$$10$$$ ($$$1$$$), and $$$13$$$–$$$16$$$ to $$$00$$$ ($$$0$$$).