디리클레 $k$제곱근

수학자 Pang은 이전 캠프에서 디리클레 합성곱을 배웠다. 하지만 심층 강화 학습에 비하면 그것은 그에게 너무 쉬웠다. 그래서 그는 특별한 일을 했다.

$f,g: \{1,2,\ldots,n\} \to \mathbb {Z}$가 양의 정수에서 정수로 가는 두 함수라면, 디리클레 합성곱 $f \* g$는 다음과 같이 정의되는 새로운 함수이다. $(f \* g)(n) =\sum\_{d \mid n}f(d)g ({\frac {n}{d}}) .$

함수 $g=f^k$의 $k$제곱을 다음과 같이 정의한다. $f^{k}=\underbrace {f \* \dots \* f} \_{k {\textrm {times}}}.$

이 문제에서는 역문제를 푼다. $g$와 $k$가 주어졌을 때, $g=f^k$를 만족하는 함수 $f$를 찾아야 한다.

또한 $f(1)$과 $g(1)$은 $1$이어야 한다는 추가 조건이 있다. 모든 연산은 $p=998244353$인 $\mathbb{F}\_{p}$에서 수행된다. 즉 디리클레 합성곱에서 $(f \* g)(n) =\left(\sum\_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$이다.

첫째 줄에 두 정수 $n$과 $k$가 주어진다. $(2\leq n\leq 10^5,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)<998244353, f(1)=1)$ 해가 여러 개면 아무거나 출력한다.