Polynomial Square Root Modulo xⁿ

Given a polynomial \(A(x)\) of degree \(n-1\) with coefficients modulo \(998244353\), find a polynomial \(B(x)\) such that

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

i.e. the first \(n\) coefficients of \(B(x)^2\) and \(A(x)\) are identical. It is guaranteed that a solution exists (in particular, \(A(0)\) is a quadratic residue modulo \(998244353\)).

The operations on the polynomial coefficients are performed modulo \(998244353\).

inputFormat

The first line contains an integer \(n\) \( (1 \leq n \leq \text{small limit})\), which is the number of coefficients of the polynomial \(A(x)\). The next line contains \(n\) space-separated integers, representing the coefficients \(A_0, A_1, \ldots, A_{n-1}\) of \(A(x)\) (where the polynomial is \(A(x)=A_0+A_1x+\cdots+A_{n-1}x^{n-1}\)).

outputFormat

Output \(n\) space-separated integers representing the coefficients \(B_0, B_1, \ldots, B_{n-1}\) of \(B(x)\) which satisfies \(B(x)^2 \equiv A(x) \pmod{x^n}\).

sample

1
4

2

</p>