【模板】多项式开根（加强版）
题目背景
模板题，无背景
题目描述
给定一个 $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,\cdots ,a_{n-1}$
**不保证$a_0=1$，但保证$a_0$是$\bmod\ 998244353$下的二次剩余。**
输出格式
输出 $n$ 个非负整数，表示答案多项式的系数$b_0,b_1\cdots ,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
说明
对于$25\%$的数据，有$n \leq 1000$
对于$50\%$的数据，有$n \leq 10^4$
对于$75\%$的数据，有$n \leq 5\times 10^4$
对于$100\%$的数据，有$n \leq 10^5,a_i \in [0,998244352] \cap \mathbb{Z}$