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

Если $f, g : \{1, 2, \dots, n\} \to \mathbb{Z}$ — две функции из множества положительных целых чисел в целые числа, то свёртка Дирихле $f * g$ — это новая функция, определяемая как:

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

Мы определяем $k$-ю степень функции $g = f^k$ как

$$f^k = \underbrace{f * \dots * f}_{k \text{ раз}}$$

В этой задаче мы хотим решить обратную задачу: по заданным $g$ и $k$ необходимо найти функцию $f$ такую, что $g = f^k$.

Более того, существует дополнительное ограничение: $f(1)$ и $g(1)$ должны быть равны $1$. Все арифметические операции выполняются в поле $\mathbb{F}_p$, где $p = 998244353$, что означает, что в свёртке Дирихле

$$(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 4 2 5 3