Background

This is a template problem, with no background.

Problem Description

Given a polynomial $A(x)$ of degree $n - 1$, find a polynomial $B(x)$ modulo $x^n$ such that $B^2(x) \equiv A(x) \pmod{x^n}$. If there are multiple solutions, output the one with the smaller constant-term coefficient.

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, \dots, a_{n-1}$ of the polynomial in order.

It is guaranteed that $a_0 = 1$.

Output Format

Output $n$ integers, representing the coefficients $b_0, b_1, \dots, b_{n-1}$ of the answer polynomial.

3
1 2 1

1 1 0

7
1 8596489 489489 4894 1564 489 35789489  

1 503420421 924499237 13354513 217017417 707895465 411020414

Hint

For $100\%$ of the testdata: $1 \le n \le 10^5$, $0 \le a_i < 998244353$.

Translated by ChatGPT 5