問題文

正整数 M が与えられます。x = 0, 1, \dots, M - 1 について次の問題を解いてください。

• y ^ 3 \equiv x \pmod{M} を満たす M 未満の非負整数 y を 1 個出力してください。ただし、そのような y が存在しない場合は -1 を出力してください。

制約

• M は 1 以上 10^6 以下の整数

入力例 1

4

出力例 1

2
1
-1
3

各 x に対する答えは次の通りです。

• x = 0 のとき、y = 2 とすると 2^3 = 8 \equiv 0 \pmod{4} が成り立ちます。よって y = 2 を出力します。
• x = 1 のとき、y = 1 とすると 1^3 = 1 \equiv 1 \pmod{4} が成り立ちます。よって y = 1 を出力します。
• x = 2 のとき、条件を満たす y は存在しません。よって -1 を出力します。
• x = 3 のとき、y = 3 とすると 3^3 = 27 \equiv 3 \pmod{4} が成り立ちます。よって y = 3 を出力します。

入力例 2

7

出力例 2

0
4
-1
-1
-1
-1
6

入力例 3

10

出力例 3

0
1
8
7
4
5
6
3
2
9