To jest trudniejsza wersja zadania Dirichlet $k$-th root z zawodów The 2019 ICPC Asia East Continent Final Contest.

Matematyk Pang nauczył się splotu Dirichleta podczas poprzedniego obozu. Jednak w porównaniu z głębokim uczeniem przez wzmacnianie, jest to dla niego zbyt łatwe. Dlatego zrobił coś specjalnego.

Jeśli $f,g: \{1,2,\ldots,n\} \to \mathbb {Z} $ są dwiema funkcjami z liczb całkowitych dodatnich w liczby całkowite, splot Dirichleta $f * g$ jest nową funkcją zdefiniowaną jako: $$(f * g)(n) =\sum_{d \mid n}f(d)g ({\frac {n}{d}}) .$$

Definiujemy $k$-tą potęgę funkcji $g=f^k$ jako $$ f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {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 dodatkowe ograniczenie, ż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 \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$.

Wejście

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

Druga linia zawiera $n$ liczb całkowitych $g(1), g(2),..., 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), ..., f(n)$ ($0\le f(i) < 998\,244\,353$, $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

Scoring

• Subtask 1 (50 punktów): $n \leq 10^5$
• Subtask 2 (50 punktów): Brak dodatkowych ograniczeń