406648: GYM102471 C Dirichlet $k$-th root

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: $$$$$$(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, $$$(f * g)(n) =\left(\sum_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$$$.

The first line contains two integers $$$n$$$ and $$$k~(2\leq n\leq 10^5,1\leq k<998244353)$$$ .

The second line contains n integers $$$g(1), g(2),..., g(n)$$$ ($$$0\le g(i)<998244353, g(1)=1$$$).

If there is no solution, output $$$-1$$$.

Otherwise, output $$$f(1), f(2), ..., f(n)$$$ ($$$0\le f(i)<998244353, f(1)=1$$$). If there are multiple solutions, print anyone.

5 2
1 8 4 26 6

1 4 2 5 3