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

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

$$(f * g)(n) = \sum_{d|n} f(d)g\left(\frac{n}{d}\right)$$

関数の $k$ 乗 $g = f^k$ を次のように定義します。

$$f^k = \underbrace{f * \dots * f}_{k \text{ times}}$$

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

さらに、$f(1)$ と $g(1)$ は $1$ でなければならないという追加の制約があります。また、すべての算術演算は $p = 998244353$ を法とする体 $\mathbb{F}_p$ 上で行われます。つまり、ディリクレ畳み込みにおいて、

$$(f * g)(n) = \left(\sum_{d|n} f(d)g\left(\frac{n}{d}\right)\right) \pmod p$$

となります。

入力

1行目に2つの整数 $n$ と $k$ ($2 \le n \le 10^5$, $1 \le k < 998244353$) が与えられます。 2行目に $n$ 個の整数 $g(1), g(2), \dots, g(n)$ ($0 \le g(i) < 998244353$, $g(1) = 1$) が与えられます。

出力

解が存在しない場合は $-1$ を出力してください。 そうでない場合は、$f(1), f(2), \dots, f(n)$ ($0 \le f(i) < 998244353$, $f(1) = 1$) を出力してください。複数の解が存在する場合は、そのうちのどれを出力しても構いません。

入出力例

入力 1

5 2
1 8 4 26 6

出力 1

1 4 2 5 3