Polynomial Square Root Modulo x^n

Given a polynomial \(A(x)\) of degree \(n-1\), find a polynomial \(B(x)\) satisfying

\[ B(x)^2 \equiv A(x) \pmod{x^n}, \]

where all operations on the coefficients are performed modulo \(998244353\). If there are multiple solutions, choose the one whose constant term is minimal.

inputFormat

The first line contains an integer \(n\) (the number of coefficients). The second line contains \(n\) space-separated integers \(a_0, a_1, \ldots, a_{n-1}\) representing the coefficients of \(A(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}\) modulo \(998244353\).

outputFormat

Output \(n\) space-separated integers \(b_0, b_1, \ldots, b_{n-1}\) representing the coefficients of \(B(x) = b_0 + b_1 x + \cdots + b_{n-1} x^{n-1}\) satisfying \(B(x)^2 \equiv A(x) \pmod{x^n}\).

sample

1
1

1