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}$. If there are multiple solutions, take the one with the smaller constant term as the answer.

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$ lines contain integers, representing the coefficients $a_0, a_1, \dots, a_{n-1}$ of the polynomial.

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.

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 $100\%$ of the data: $1 \le n \leq 10^5$, $0 \le a_i < 998244353$.

见题面 Input 部分

见题面 Output 部分