Description

庞数学家在上一次集训中学习了狄利克雷卷积。不过，相比深度强化学习，这对他来说太简单了。因此，他做了一些特别的事情。

如果 $f,g: \{1,2,\ldots,n\} \to \mathbb {Z}$ 是从正整数到整数的两个函数，则狄利克雷卷积 $f * g$ 定义为一个新函数：

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

我们定义函数 $g=f^k$ 的 $k$ 次幂为

$$f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {次}}}.$$

在本题中，我们要求解逆问题：给定 $g$ 和 $k$，你需要找到一个函数 $f$，使得 $g=f^k$。

此外，还有一个额外的限制条件：$f(1)$ 和 $g(1)$ 必须等于 $1$。所有的算术运算都在 $\mathbb{F}_{p}$ 上进行，其中 $p=998244353$，也就是说，在狄利克雷卷积中，$(f * g)(n) =\left(\sum_{d \mid n}f(d)g \left(\frac {n}{d}\right)\right) \bmod p$。

Input Format

第一行包含两个整数 $n$ 和 $k~(2\leq n\leq 10^5,1\leq k<998244353)$。

第二行包含 $n$ 个整数 $g(1), g(2),..., g(n)$（$0\le g(i)<998244353, g(1)=1$）。

Output Format

如果无解，输出 $-1$。

否则，输出 $f(1), f(2), ..., f(n)$（$0\le f(i)<998244353, f(1)=1$）。如果有多组解，输出任意一组即可。

5 2
1 8 4 26 6

1 4 2 5 3

Hint

由 ChatGPT 4.1 翻译