Tokitsukaze 正在玩 SkywalkerT 设计的密室逃脱游戏。在这个游戏中,她需要找出房间里隐藏的线索,找到逃生的方法。
过了一会儿,她意识到逃跑的唯一方法就是打开数字门锁,因为她不小心进入了一个秘密隔间,并发现了一些线索,可以解释为:
- 只有输入$$$n$$$可能不同的密码才能开门;
- 密码必须是 $$$0$$$ 到 $$$(m - 1)$$$ 之间的整数;
- 如果 $$$x$$$ 和 $$$m$$$ 不是互质的(即 $$$x$$$ 和 $$$m$$$ 有大于 $$$1$$$ 的公约数),则密码不能是 $$$x$$$ ($$$0 \leq x < m$$$);
- 如果存在非负整数 $$$e$$$ 和 $$$k$$$ 使得 $$$p^e = k m + x$$$,则密码不能为 $$$x$$$ ($$$0 \leq x < m$$$),其中 $$$p$$$ 是秘密整数;
- 任何不违反上述规则的整数都可以作为密码;
- 房间里隐藏着几个整数,但其中只有一个可以是$$$p$$$。
幸运的是,她发现锁中记录了$$$n$$$和$$$m$$$。然而,令时风沮丧的是她数学成绩不好。现在她发现了一个疑似$$$p$$$的整数,她希望你帮她找出$$$n$$$可能的密码,或者确定该整数不可能是$$$p$$$。
输入
唯一的一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$p$$$ ($$$1 \leq n \leq 5 \times 10^5$$$、$$$1 \leq p < m \leq 10^{18}$$$)。
保证 $$$m$$$ 是单个素数的正整数幂。
输出
如果可能的不同密码的数量小于 $$$n$$$,则打印单个整数 $$$-1$$$。
否则,打印 $$$n$$$ 范围从 $$$0$$$ 到 $$$(m - 1)$$$ 的不同整数作为密码。您可以按任何顺序打印这些整数。另外,如果有多个解,则打印任意一个。
示例
输入 #1
1 2 1
输出 #1
-1
输入 #2
3 5 1
输出 #2
2 4 3
输入 #3
2 5 4
输出 #3
2 3
输入#4
4 9 8
输出#4
2 4 7 5
注意
在第一个示例中,没有可能的密码。
在最后三个示例中,给定的整数 $$$n$$$ 等于给定整数 $$$m$$$ 和 $$$p$$$ 可能的不同密码的数量,因此,如果忽略输出中数字的顺序,则解决方案是唯一的,如上所示。