Problem Description

Given a polynomial $A(x)$ of degree $n-1$, find a polynomial $B(x)$ in the $\bmod\ {x^n}$ sense such that $B^2(x)\equiv A(x)\pmod {x^n}$.

The coefficients of the polynomial are computed in the $\bmod\ 998244353$ sense.

Input Format

The first line contains a positive integer $n$.

The next $n$ integers represent the coefficients $a_0, a_1, \cdots, a_{n-1}$ of the polynomial.

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, \cdots, b_{n-1}$ of the answer polynomial. If there are multiple solutions, output the one with the lexicographically smallest coefficient sequence.

Sample Input and Output

Sample Input #1

3
1 2 1

Sample Output #1

1 1 0

Sample Input #2

7
1 8596489 489489 4894 1564 489 35789489

Sample Output #2

1 503420421 924499237 13354513 217017417 707895465 411020414

Notes

For $25\%$ of the data, $n \leq 1000$.

For $50\%$ of the data, $n \leq 10^4$.

For $75\%$ of the data, $n \leq 5 \times 10^4$.

For $100\%$ of the data, $n \leq 10^5$ and $a_i \in [0, 998244352] \cap \mathbb{Z}$.

见题面 Input 部分

见题面 Output 部分