Description

ZJ学姐最近在备战考研的过程中同时备战ecfinal，在之前的课程中学习了$\texttt{Dirichlet}$卷积。但与图论建图相比，这对她来说太简单了。因此，她做了一些特别的事情。

若 $f,g: \{1,2,\ldots,n\} \to \mathbb {Z}$ 是两个从正整数到整数的函数，则$\texttt{Dirichlet}$卷积是一个新函数，定义为:

$(f * g)(n) =\sum_{d \mid n}f(d)g ({\frac {n}{d}})$ 。

我们定义函数的 $k$ -次幂 $g=f^k$ 是 $f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {次}}}。$

在这个问题中，我们想要解决相反的问题：给定 $g$ 和 $k$ ，你需要找到一个函数 $f$ ，使 $g=f^k$ 。

此外，还有 $f(1)$ 和 $g(1)$ 必须等于 $1$ 的附加约束。所有的算术运算都是在 $\mathbb{F}_{p}$ 上完成的，其中 $p=998244353$ ，这意味着在Dirichlet卷积中：

$(f * g)(n) =\left(\sum_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$ 。

Input Format

第一行输入一个数字 $t$ ，代表一共有 $t$ 组样例 $(1\leq t\leq 100)$。

对于每组样例来说输入两行。

第一行包含两个整数 $n$ 和 $k(2\leq n\leq 10^5, 1\leq k < 998244353)$ 。

第二行包含n个整数 $g(1), g(2),\dots, g(n)$ ( $0\le g(i) < 998244353, g(1)=1$ ) 。

题目保证 $\sum n \le 10^5$。

Output Format

如果没有解决方案，则输出 $-1$ 。

否则，输出 $f(1), f(2), ..., f(n)$ ($0 \le f(i) < 998244353, f(1)=1$)。如果有多种解决方案，请随便选一个。

请注意：每行输出的末尾不允许有空格。

1
5 2
1 8 4 26 6

1 4 2 5 3