Matematyk Pang poznał splot Dirichleta podczas poprzedniego obozu. Jednak w porównaniu z głębokim uczeniem przez wzmacnianie, wydało mu się to zbyt łatwe. Dlatego zrobił coś specjalnego.

Jeśli $f, g : \{1, 2, \dots, n\} \to \mathbb{Z}$ są dwiema funkcjami z liczb całkowitych dodatnich w liczby całkowite, to splot Dirichleta $f * g$ jest nową funkcją zdefiniowaną jako:

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

Definiujemy $k$-tą potęgę funkcji $g = f^k$ jako:

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

W tym zadaniu chcemy rozwiązać problem odwrotny: mając dane $g$ oraz $k$, należy znaleźć funkcję $f$ taką, że $g = f^k$.

Ponadto istnieje dodatkowy warunek, że $f(1)$ oraz $g(1)$ muszą być równe $1$. Wszystkie operacje arytmetyczne wykonywane są w ciele $\mathbb{F}_p$, gdzie $p = 998244353$, co oznacza, że w splocie Dirichleta:

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

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 10^5$, $1 \le k < 998244353$).

Druga linia zawiera $n$ liczb całkowitych $g(1), g(2), \dots, g(n)$ ($0 \le g(i) < 998244353$, $g(1) = 1$).

Wyjście

Jeśli rozwiązanie nie istnieje, wypisz $-1$.

W przeciwnym razie wypisz $f(1), f(2), \dots, f(n)$ ($0 \le f(i) < 998244353$, $f(1) = 1$). Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 1

5 2
1 8 4 26 6

Wyjście 1

1 4 2 5 3