AT_highrate2025_b 三乗根

正整数 $ M $ が与えられます。 $ x = 0, 1, \dots, M - 1 $ について次の問題を解いてください。 - $ y ^ 3 \equiv x \pmod{M} $ を満たす $ M $ 未満の非負整数 $ y $ を $ 1 $ 個出力してください。ただし、そのような $ y $ が存在しない場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ M $

$ M $ 行出力せよ。 $ i $ 行目には $ x = i - 1 $ の時の答えを出力せよ。 なお、答えが複数存在する場合はどれを出力しても良い。

### Sample Explanation 1 各 $ 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 $ を出力します。 ### Constraints - $ M $ は $ 1 $ 以上 $ 10^6 $ 以下の整数