Background

This is a template problem, with no background.

Problem Description

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$.

Input Format

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 Format

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).

3
1 2 1

1 1 0

7
1 8596489 489489 4894 1564 489 35789489  

1 503420421 924499237 13354513 217017417 707895465 411020414

Hint

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