题目描述

题面参考 Codeforces Gym 102471 C. Dirichlet $k$-th root。

请注意，唯一的不同为数据范围。

定义两个函数 $f, g: {1, 2, \dots, n} \rightarrow \mathbb Z$ 的狄利克雷卷积 $f * g$ 为：

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

我们定义 $g = f^k$ 即 $k$ 次幂为：

$$ f^{k}=\underbrace {f \dots f} _{k~{\textrm {个}}} $$

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

另外，保证 $g(1)=1$，你需要保证 $f(1)=1$。所有的运算在 $\mathbb Fp$ 上进行，其中 $p = 998244353$，这意味着狄利克雷卷积为 $(f*g)(n) = \left(\sum{d|n} f(d)g(\frac nd)\right) \bmod p$。

输入格式

第一行输入两个正整数 $n, k$。

第二行输入 $n$ 个整数，$g(1), g(2), \dots, g(n)$，保证 $0\le g(i) < 998244353, g(1) = 1$。

输出格式

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

否则，一行输出 $n$ 个整数 $f(1), f(2), \dots, f(n)$，要求 $0\le f(i) < 998244353, f(1)=1$，如果有多个解，你只需要输出任意一个。

样例

input

5 2
1 8 4 26 6

output

1 4 2 5 3

数据范围与提示

对于 $50\%$ 的数据，保证 $n\le 10^5$。

对于 $100\%$ 的数据，保证 $2\le n\le 10^6, 1\le k < 998244353$。