形式幂级数开方（稀疏）

【题目描述】

给定形式幂级数 $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998244353}[[x]]$。 $f$ 中只有 $K$ 个系数非零，输入只给出这些非零系数 $a_{i_k}$。

请计算 $f(x)$ 的一个平方根的前 $N$ 项。也就是说，求 $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998244353}[[x]]$ 使得

【输入】

$N$ $K$
$i_0$ $a_{i_0}$
$\vdots$
$i_{K-1}$ $a_{i_{K-1}}$

【输出】

若不存在满足条件的 $g(x)$，输出

-1

若存在这样的 $g(x)$，任意选定一个并输出

$b_0$ $b_1$ $\cdots$ $b_{N - 1}$

【输入样例】

4 2
2 9
3 12

【输出样例】

0 998244350 998244351 0

【输入样例2】

4 2
2 10
3 12

【输出样例2】

-1

【输入样例3】

5 0

【输出样例3】

0 0 0 0 0

【数据范围】

• $1 \leq N \leq 1000000$
• $0 \leq K \leq 10$
• $0 \leq i_0 < \cdots < i_{K-1} \leq N - 1$
• $1 \leq a_{i_k} < 998244353$

【来源】

Library Checker（yosupo06） sqrt_of_formal_power_series_sparse

本题为 special judge（输出任意合法解），暂不可本地评测。