【模板】多项式除法

题目描述

给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$ ,请求出多项式 $Q(x)$, $R(x)$,满足以下条件: - $Q(x)$ 次数为 $n-m$,$R(x)$ 次数小于 $m$ - $F(x) = Q(x) * G(x) + R(x)$ 所有的运算在模 $998244353$ 意义下进行。

输入输出格式

输入格式


第一行两个整数 $n$,$m$,意义如上。 第二行 $n+1$ 个整数,从低到高表示 $F(x)$ 的各个系数。 第三行 $m+1$ 个整数,从低到高表示 $G(x)$ 的各个系数。

输出格式


第一行 $n-m+1$ 个整数,从低到高表示 $Q(x)$ 的各个系数。 第二行 $m$ 个整数,从低到高表示 $R(x)$ 的各个系数。 如果 $R(x)$ 不足 $m-1$ 次,多余的项系数补 $0$。

输入输出样例

输入样例 #1

5 1
1 9 2 6 0 8
1 7

输出样例 #1

237340659 335104102 649004347 448191342 855638018
760903695

说明

对于所有数据,$1 \le m < n \le 10^5$,给出的系数均属于 $[0, 998244353) \cap \mathbb{Z}$。