【模板】多项式乘法(FFT)

题目背景

这是一道 FFT 模板题

题目描述

给定一个 $n$ 次多项式 $F(x)$,和一个 $m$ 次多项式 $G(x)$。 请求出 $F(x)$ 和 $G(x)$ 的卷积。

输入输出格式

输入格式


第一行 $2$ 个正整数 $n,m$。 接下来一行 $n+1$ 个数字,从低到高表示 $F(x)$ 的系数。 接下来一行 $m+1$ 个数字,从低到高表示 $G(x)$ 的系数。

输出格式


一行 $n+m+1$ 个数字,从低到高表示 $F(x)*G(x)$ 的系数。

输入输出样例

输入样例 #1

1 2
1 2
1 2 1

输出样例 #1

1 4 5 2

说明

保证输入中的系数大于等于 $0$ 且小于等于 $9$。 对于100%的数据:$n, m \leq {10}^6$。