Mathematician Pang 在之前的營隊中學習了 Dirichlet 卷積。然而，與深度強化學習相比，這對他來說太簡單了。因此，他做了一些特別的事情。

若 $f, g : \{1, 2, \dots, n\} \to \mathbb{Z}$ 是兩個從正整數映射到整數的函數，則 Dirichlet 卷積 $f * g$ 定義為一個新的函數：

$$(f * g)(n) = \sum_{d|n} f(d)g\left(\frac{n}{d}\right)$$

我們定義函數 $g = f^k$ 的 $k$ 次方為：

$$f^k = \underbrace{f * \dots * f}_{k \text{ times}}$$

在這個問題中，我們想要解決反問題：給定 $g$ 和 $k$，你需要找到一個函數 $f$ 使得 $g = f^k$。

此外，還有一個額外的限制，即 $f(1)$ 和 $g(1)$ 必須等於 $1$。所有的算術運算都在 $\mathbb{F}_p$ 上進行，其中 $p = 998244353$，這意味著在 Dirichlet 卷積中：

$$(f * g)(n) = \left(\sum_{d|n} f(d)g\left(\frac{n}{d}\right)\right) \pmod p$$

輸入格式

第一行包含兩個整數 $n$ 和 $k$ ($2 \le n \le 10^5, 1 \le k < 998244353$)。 第二行包含 $n$ 個整數 $g(1), g(2), \dots, g(n)$ ($0 \le g(i) < 998244353, g(1) = 1$)。

輸出格式

如果沒有解，輸出 $-1$。 否則，輸出 $f(1), f(2), \dots, f(n)$ ($0 \le f(i) < 998244353, f(1) = 1$)。如果有多個解，輸出其中任意一個即可。

範例

輸入 1

5 2
1 8 4 26 6

輸出 1

1 4 2 5 3