#50. 多项式乘法

题目类型:传统型 时间限制:1000 ms 空间限制:256 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

这是一道模板题。

给你两个多项式,请输出乘起来后的多项式,系数对 $998244353$ 取模。


输入格式

第一行两个整数 $n$ 和 $m$,分别表示两个多项式的次数 $+\ 1$。

第二行 $n$ 个整数,分别表示第一个多项式的 $0$ 到 $n\ -\ 1$ 次项前的系数。

第三行 $m$ 个整数,分别表示第二个多项式的 $0$ 到 $m\ -\ 1$ 次项前的系数。

输出格式

一行 $n\ +\ m\ -\ 1$ 个整数,分别表示乘起来后的多项式的 $0$ 到 $n\ +\ m\ -\ 2$ 次项前的系数。


样例一

Input

2 3
1 2
1 2 1

Output

1 4 5 2

Explanation

$(1\ +\ 2x)\cdot(1\ +\ 2x\ +\ x^2)\ =\ 1\ +\ 4x\ +\ 5x^2\ +\ 2x^3$


限制与约定

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

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

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