C-Dirichlet k -th root_The 2019 ICPC Asia-East Continent Final（重现赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\textit{Mathematician Pang}$ learned Dirichlet convolution during the previous camp. However, compared with deep reinforcement learning, it's too easy for him. Therefore, he did something special.
If $f,g: \{1,2,\ldots,n\} \to \mathbb {Z}$ are two functions from the positive integers to the integers, the Dirichlet convolution ${f * g}$ is a new function defined by:
$\displaystyle (f * g)(n) =\sum_{d \mid n}f(d)g ({\frac {n}{d}}) .$
We define the k-th power of an function $g=f^k$ by
$f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {times}}}.$
In this problem, we want to solve the inverse problem: Given ${g}$ and ${k}$ , you need to find a function ${f}$ such that $g=f^k$ .

Moreover, there is an additional constraint that ${f(1)}$ and ${g(1)}$ must equal to ${1}$ . And all the arithmetic operations are done on $\mathbb{F}_{p}$ where ${p=998244353}$ , which means that in the Dirichlet convolution, $\displaystyle (f * g)(n) =\left(\sum_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$ .

输入描述:

The first line contains two integers  and  .
The second line contains n integers  ().

输出描述:

If there is no solution, output .
Otherwise, output  (). If there are multiple solutions, print anyone.

示例1

输入

复制

5 2
1 8 4 26 6

输出

复制

1 4 2 5 3