#54. 多项式开方

这是一道模板题。

给定最高次数为$n\ -\ 1$的多项式 $A(x)$，你要求出 $B(x)$ 使得 $B(x)^2\ -\ A(x)\ \equiv\ 0\pmod{x^n}$，且次数不超过 $n\ -\ 1$，且常数项为 $1$ 。保证 $A(x)$ 常数项为 $1$，系数对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，分别表示 $A(x)$ 的 $0$ 到 $n\ -\ 1$ 次项前的系数。

输出格式

一行 $n$ 个整数，表示 $B(x)$ 的 $0$ 到 $n\ -\ 1$ 次项前的系数。

样例一

input

2
1 2

output

1 1

explanation

$(1\ +\ x)^2\ \equiv\ 1\ +\ 2x\pmod{x^2}$

限制与约定

对于 $100\%$ 的数据，满足 $1\ \leq\ n\ \leq\ 100000$，保证输入中的系数大于等于 $0$ 且小于 $998244353$，且常数项系数为 $1$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$