This is a harder version of Dirichlet $k$-th root from The 2019 ICPC Asia East Continent Final Contest.

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 {\color{red}{\mathbf{10^6}}},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) < 998\,244\,353$, $f(1)=1$). If there are multiple solutions, print anyone.

Example

Input

5 2
1 8 4 26 6

Output

1 4 2 5 3

Scoring

• Subtask 1 (50 points): $n \leq 10^5$
• Subtask 2 (50 points): No additional constraints