【模板】多项式开根
题目背景
模板题，无背景
题目描述
给定一个$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}$