P5277 [Template] Polynomial Square Root (Enhanced Version)

This is a template problem, with no background.

Given an $(n - 1)$-degree polynomial $A(x)$, find a polynomial $B(x)$ modulo $x^n$ such that $B^2(x)\equiv A(x)\pmod {x^n}$. All polynomial coefficients are computed modulo $998244353$.

The first line contains a positive integer $n$. The next line contains $n$ integers, representing the coefficients $a_0,a_1,\ldots ,a_{n-1}$ in order. **It is not guaranteed that $a_0=1$, but it is guaranteed that $a_0$ is a quadratic residue modulo $998244353$.**

Output $n$ non-negative integers, representing the coefficients $b_0,b_1,\ldots ,b_{n-1}$ of the answer polynomial. If there are multiple solutions, output the one with the smallest lexicographical order of the **coefficient sequence** (not the character sequence).

For $25\%$ of the testdata, $n \leq 1000$. For $50\%$ of the testdata, $n \leq 10^4$. For $75\%$ of the testdata, $n \leq 5\times 10^4$. For $100\%$ of the testdata, $n \leq 10^5$, and $a_i \in [0,998244352] \cap \mathbb{Z}$. Translated by ChatGPT 5