#51. 多项式除法

这是一道模板题。

给定两个多项式 $A(x),\ B(x)$，你要求出 $C(x),\ D(x)$ 使得 $A(x)\ =\ B(x)\ \cdot\ C(x)\ +\ D(x)$，且 $D(x)$ 的最高次数小于 $B(x)$ 的最高次数，对 $998244353$ 取模。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示 $A(x),\ B(x)$ 次数 $+\ 1$。

第二行 $n$ 个整数，分别表示 $A(x)$ 的 $0$ 到 $n\ -\ 1$ 次项前的系数。

第三行 $m$ 个整数，分别表示 $B(x)$ 到 $0$ 到 $m\ -\ 1$ 次项前的系数。

输出格式

两行，第一行输出 $n\ -\ m\ +\ 1$ 个数表示 $C(x)$，第二行输出 $m\ -\ 1$ 个数表示 $D(x)$。

样例一

Input

3 2
1 2 1
1 2

Output

249561089 499122177
748683265

Explanation

$x\ +\ 2x\ +\ x^2\ =\ (1\ +\ 2x)\cdot(249561089\ +\ 499122177x)\ +\ 748683265$

注意要对 $998244353$ 取模

限制与约定

对于 $100\%$ 的数据，满足 $1\ < m\ < n\ \leq\ 10^5$，保证输入中的系数大于等于 $0$ 且小于 $998244353$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$