这是 2019 ICPC 亚洲东部大陆决赛 中 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}}) .$$

我们定义函数 $g=f^k$ 为 $f$ 的 $k$ 次幂：$$ f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {times}}}.$$

在本题中，我们需要解决逆问题：给定 $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 ({\frac {n}{d}})\right) \bmod p$。

输入格式

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

第二行包含 $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 分)：无额外限制