【模板】多项式开根

题目背景

模板题,无背景

题目描述

给定一个$n-1$次多项式$A(x)$,求一个在$\bmod\ x^n$意义下的多项式$B(x)$,使得$B^2(x) \equiv A(x) \ (\bmod\ x^n)$ 多项式的系数在$\bmod\ 998244353$的意义下进行运算。

输入输出格式

输入格式


第一行一个正整数$n$。 接下来$n$个整数,依次表示多项式的系数$a_0, a_1, \dots, a_{n-1}$ 保证$a_0 = 1$.

输出格式


输出$n$个整数,表示答案多项式的系数$b_0, b_1, \dots, b_{n-1}$

输入输出样例

输入样例 #1

3
1 2 1

输出样例 #1

1 1 0

输入样例 #2

7
1 8596489 489489 4894 1564 489 35789489  

输出样例 #2

1 503420421 924499237 13354513 217017417 707895465 411020414

说明

对于$100\%$的数据:$n \leq 10^5 \qquad a_i \in [0,998244352] \cap \mathbb{Z}$