$$$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$$$;
- 所有在 1/8 决赛中被淘汰的球队都获得 $$$9$$$ 名额,依此类推。
例如,这张图描述了锦标赛 $$$k = 3$$$ 的可能方式之一,以及球队的最终名次:
按照上述规则进行的锦标赛结束后,其结果按以下方式编码。令 $$$p_i$$$ 为第 $$$i$$$ 队在锦标赛中的位置。锦标赛的哈希值 $$$h$$$ 计算如下: $$$h = (\sum \limits_{i=1}^{2^k} i \cdot A^{p_i}) \bmod 998244353$$$,其中 $$$A$$$ 是某个给定的整数。
不幸的是,由于系统崩溃,几乎所有与锦标赛相关的数据都丢失了。唯一保留的数据是 $$$k$$$、$$$A$$$ 和 $$$h$$$ 的值。如果可能的话,您需要恢复球队在锦标赛中的最终排名。
输入
唯一的一行包含三个整数 $$$k$$$、$$$A$$$ 和 $$$h$$$ ($$$1 \le k \le 5$$$; $$$100 \le A \le 10^8$$$; $$$0 \le h \le 998244352$$$)。
输出
如果无法找到与您拥有的数据一致的球队名次,请打印一个整数$$$-1$$$。
否则,打印 $$$2^k$$$ 整数,其中第 $$$i$$$ 个整数应等于 $$$p_i$$$ (第 $$$i$$$ 队的位置)。请注意,您的答案应该与锦标赛可能进行的一种可能的方式一致,并注意锦标赛的初始结构是固定的(例如,$$$1$$$ 和 $$$2$$$ 团队始终在锦标赛的第一阶段相互比赛)。如果有多种方法可以恢复与您拥有的数据一致的球队位置,请打印其中任何一种。
示例
输入 #1
3 1337 75275197
输出 #1
5 3 5 2 1 5 5 3
输入 #2
2 100 5040100
输出 #2
1 3 3 2
输入 #3
2 100 7020100
输出 #3
-1
注意
声明中描述了第一个示例的锦标赛。
对于第三个示例,排名 $$$[1, 2, 3, 3]$$$(团队 $$$1$$$ 获得位置 $$$1$$$,团队 $$$2$$$ 获得位置 $$$2$$$,团队 $$$3$$$ 和 $$$4$$$ 获得位置 $$$3$$$)可能会导致哈希值$$$7020100$$$,其中$$$A = 100$$$,但任何锦标赛都不可能获得这样的名次,因为$$$1$$$ 和$$$2$$$ 队在半决赛中互相交锋,因此他们无法获得两个第一名。