[AdditionalFile6713.zip](file://AdditionalFile6713.zip?type=additional_file)

#6713. 「EC Final 2019」狄利克雷 k 次根 加强版

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题面参考 EC-Final 2019 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 F_p$ 上进行，其中 $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$，如果有多个解，你只需要输出任意一个。

样例

输入

5 2
1 8 4 26 6

输出

1 4 2 5 3

数据范围与提示

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

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