この問題は、The 2019 ICPC Asia East Continent Final Contest における Dirichlet $k$-th root の難易度が高いバージョンです。

Mathematician Pang は前回のキャンプでディリクレ畳み込みを学びました。しかし、深層強化学習と比較すると、彼にとってそれは簡単すぎました。そこで、彼は特別なことをしました。

$f,g: \{1,2,\ldots,n\} \to \mathbb {Z} $ を正の整数から整数への関数とするとき、ディリクレ畳み込み $f * g$ は次のように定義される新しい関数です。 $$(f * g)(n) =\sum_{d \mid n}f(d)g ({\frac {n}{d}}) .$$

関数の $k$ 乗 $g=f^k$ を次のように定義します。 $$ f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {times}}}.$$

この問題では、逆問題を解く必要があります。すなわち、関数 $g$ と $k$ が与えられたとき、$g=f^k$ を満たす関数 $f$ を求めてください。

さらに、$f(1)$ と $g(1)$ は $1$ に等しいという追加の制約があります。すべての算術演算は $p=998244353$ を法とする $\mathbb{F}_{p}$ 上で行われます。つまり、ディリクレ畳み込みにおいて $(f * g)(n) =\left(\sum_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$ となります。

入力

1行目に2つの整数 $n$ と $k$ ($2\leq n\leq 10^6, 1\leq k < 998244353$) が与えられます。

2行目に $n$ 個の整数 $g(1), g(2),..., g(n)$ ($0\le g(i) < 998244353, g(1)=1$) が与えられます。

出力

解が存在しない場合は $-1$ を出力してください。

それ以外の場合は、$f(1), f(2), ..., f(n)$ ($0\le f(i) < 998\,244\,353, f(1)=1$) を出力してください。複数の解が存在する場合は、そのうちのいずれかを出力してください。

入出力例

入力 1

5 2
1 8 4 26 6

出力 1

1 4 2 5 3

小課題

• 小課題 1 (50点): $n \leq 10^5$
• 小課題 2 (50点): 追加の制約なし