형식적 멱급수의 제곱근

형식적 멱급수 $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}\_{998244353}[[x]]$이 주어진다. $f(x)$의 제곱근의 첫 $N$개 항을 계산한다. 다시 말해, 다음을 만족하는 $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}\_{998244353}[[x]]$을 찾는다.

$f(x) \equiv g(x)^2 \pmod{x^N}.$

제약 조건

• $1 \leq N \leq 500000$
• $0 \leq a_i < 998244353$

$N$
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$

조건을 만족하는 $g(x)$이 없다면 다음을 출력한다.

-1

그러한 $g(x)$이 존재한다면, 그중 아무거나 하나를 골라 다음을 출력한다.

$b_0$ $b_1$ $\cdots$ $b_{N - 1}$