Математик Пан изучил свертку Дирихле во время предыдущего лагеря. Однако по сравнению с глубоким обучением с подкреплением это кажется ему слишком простым. Поэтому он решил сделать кое-что особенное.

Если $f,g: \{1,2,\ldots,n\} \to \mathbb {Z} $ — две функции из множества положительных целых чисел в целые числа, то свертка Дирихле $f * g$ — это новая функция, определяемая как: $$(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$, что означает, что при свертке Дирихле $(f * g)(n) =\left(\sum_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$.

Входные данные

Первая строка содержит два целых числа $n$ и $k$ ($2\leq n\leq 10^6$, $1\leq k < 998244353$).

Вторая строка содержит $n$ целых чисел $g(1), g(2),..., g(n)$ ($0\le g(i) < 998244353$, $g(1)=1$).

Выходные данные

Если решения не существует, выведите $-1$.

В противном случае выведите $f(1), f(2), ..., f(n)$ ($0\le f(i) < 998\,244\,353$, $f(1)=1$). Если существует несколько решений, выведите любое из них.

Примеры

Входные данные 1

5 2
1 8 4 26 6

Выходные данные 1

1 4 2 5 3

Оценивание

• Подзадача 1 (50 баллов): $n \leq 10^5$
• Подзадача 2 (50 баллов): Без дополнительных ограничений