【模板】多项式开根
题目背景
模板题，无背景
题目描述
给定一个 $n-1$ 次多项式 $A(x)$，求一个在 ${} \bmod x^n$ 意义下的多项式 $B(x)$，使得 $B^2(x) \equiv A(x) \pmod{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 \%$ 的数据：$1 \le n \leq 10^5$，$0 \le a_i < 998244353$。