Mathematician Pang 在之前的训练营中学习了狄利克雷卷积（Dirichlet convolution）。然而，与深度强化学习相比，这对他来说太简单了。因此，他做了一些特别的事情。

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

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

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

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

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

此外，还有一个额外的约束条件，即 $f(1)$ 和 $g(1)$ 必须等于 $1$。所有的算术运算都在 $\mathbb{F}_p$ 上进行，其中 $p = 998244353$，这意味着在狄利克雷卷积中：

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

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 10^5, 1 \le k < 998244353$)。 第二行包含 $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