CF1569E.Playoff Restoration

$2^k$ teams participate in a playoff tournament. The tournament consists of $2^k - 1$ games. They are held as follows: first of all, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$ (exactly in this order), and so on (so, $2^{k-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{k-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, $2^{k-2}$ games are played: in the first one of them, the winner of the game "$1$ vs $2$" plays against the winner of the game "$3$ vs $4$", then the winner of the game "$5$ vs $6$" plays against the winner of the game "$7$ vs $8$", and so on. This process repeats until only one team remains.

After the tournament ends, the teams are assigned places according to the tournament phase when they were eliminated. In particular:

• the winner of the tournament gets place $1$;
• the team eliminated in the finals gets place $2$;
• both teams eliminated in the semifinals get place $3$;
• all teams eliminated in the quarterfinals get place $5$;
• all teams eliminated in the 1/8 finals get place $9$, and so on.

For example, this picture describes one of the possible ways the tournament can go with $k = 3$, and the resulting places of the teams:

After a tournament which was conducted by the aforementioned rules ended, its results were encoded in the following way. Let $p_i$ be the place of the $i$-th team in the tournament. The hash value of the tournament $h$ is calculated as $h = (\sum \limits_{i=1}^{2^k} i \cdot A^{p_i}) \bmod 998244353$, where $A$ is some given integer.

Unfortunately, due to a system crash, almost all tournament-related data was lost. The only pieces of data that remain are the values of $k$, $A$ and $h$. You are asked to restore the resulting placing of the teams in the tournament, if it is possible at all.

$2^k$ 支队伍参加一场淘汰制锦标赛。该锦标赛共进行 $2^k - 1$ 场比赛，赛程安排如下：首先将所有队伍两两分组：第 $1$ 支队伍对阵第 $2$ 支队伍，第 $3$ 支队伍对阵第 $4$ 支队伍（严格按此顺序），依此类推（因此该阶段共进行 $2^{k-1}$ 场比赛）。每场比赛中失败的队伍即被淘汰，且每场比赛恰好淘汰一支队伍（不存在平局）。该阶段结束后，仅剩 $2^{k-1}$ 支队伍。若只剩一支队伍，则其被宣布为冠军；否则继续进行 $2^{k-2}$ 场比赛：第一场由“第 $1$ 场 vs 第 $2$ 场”的胜者对阵“第 $3$ 场 vs 第 $4$ 场”的胜者，第二场由“第 $5$ 场 vs 第 $6$ 场”的胜者对阵“第 $7$ 场 vs 第 $8$ 场”的胜者，依此类推。该过程不断重复，直至仅剩一支队伍。

锦标赛结束后，各支队伍依据其被淘汰所处的轮次获得相应名次。具体规则如下：

• 锦标赛冠军（最终胜者）获得第 $1$ 名；
• 在决赛中被淘汰的队伍获得第 $2$ 名；
• 在半决赛中被淘汰的两支队伍均获得第 $3$ 名；
• 在四分之一决赛中被淘汰的所有队伍均获得第 $5$ 名；
• 在八分之一决赛中被淘汰的所有队伍均获得第 $9$ 名，依此类推。

例如，下图描述了当 $k = 3$ 时锦标赛的一种可能进行方式，以及各支队伍最终获得的名次：

在一场按上述规则进行的锦标赛结束后，其结果以如下方式编码：设 $p_i$ 表示第 $i$ 支队伍在锦标赛中获得的名次，则锦标赛的哈希值 $h$ 定义为

$$h = \left(\sum_{i=1}^{2^k} i \cdot A^{p_i}\right) \bmod 998244353,$$

其中 $A$ 是给定的某个整数。

不幸的是，由于系统崩溃，几乎所有与锦标赛相关的数据均已丢失。目前仅存的数据为 $k$、$A$ 和 $h$ 的值。你的任务是根据这些信息，还原出锦标赛中各支队伍的最终名次（即序列 $p_1, p_2, \dots, p_{2^k}$），如果该还原是可能的话。

The only line contains three integers $k$, $A$ and $h$ ($1 \le k \le 5$; $100 \le A \le 10^8$; $0 \le h \le 998244352$).

唯一一行包含三个整数 $k$、$A$ 和 $h$（$1 \le k \le 5$；$100 \le A \le 10^8$；$0 \le h \le 998244352$）。

If it is impossible to find any placing of the teams that is consistent with the data you have, print one integer $-1$.

Otherwise, print $2^k$ integers, where $i$-th integer should be equal to $p_i$ (the place of the $i$-th team). Note that your answer should be consistent with one of the possible ways the tournament could go, and note that the initial structure of the tournament is fixed (for example, teams $1$ and $2$ always play in the first phase of the tournament against each other). If there are multiple ways to restore the places of the teams which are consistent with the data you have, print any of them.

如果无法找到任何一种队伍排名方式，使其与你所拥有的数据一致，则输出一个整数 $-1$。

否则，输出 $2^k$ 个整数，其中第 $i$ 个整数应等于 $p_i$（即第 $i$ 支队伍的名次）。注意：你的答案必须与某一种可能的锦标赛进行过程一致，且锦标赛的初始结构是固定的（例如，队伍 $1$ 和队伍 $2$ 总是在锦标赛第一轮中相互对阵）。如果存在多种满足已有数据的队伍名次恢复方案，请输出其中任意一种。

The tournament for the first example is described in the statement.

For the third example, the placing $[1, 2, 3, 3]$ (team $1$ gets place $1$, team $2$ gets place $2$, teams $3$ and $4$ get place $3$) could result in a hash value of $7020100$ with $A = 100$, but no tournament can result in such placing since teams $1$ and $2$ play against each other in the semifinals, so they cannot get two first places.

第一个示例所描述的锦标赛已在题干中给出。

对于第三个示例，名次排列 $[1, 2, 3, 3]$（即队伍 $1$ 获得第 $1$ 名，队伍 $2$ 获得第 $2$ 名，队伍 $3$ 和 $4$ 并列第 $3$ 名）在 $A = 100$ 时可能产生哈希值 $7020100$，但没有任何锦标赛能产生该名次排列，因为队伍 $1$ 和 $2$ 在半决赛中相互对阵，故它们不可能分别获得第 $1$ 名和第 $2$ 名。