406648: GYM102471 C Dirichlet $k$-th root

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Dirichlet $$$k$$$-th roottime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$$$.

Input

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$$$).

Output

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.

ExampleInput
5 2
1 8 4 26 6
Output
1 4 2 5 3

加入题单

上一题 下一题 算法标签: