514001 - 多项式乘法

【题目描述】多项式乘法(FFT)

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

输入

第一行两个整数n和m(1≤n,m≤106)。 接下来一行n+1个数字,从低到高表示F(x) 的系数。 接下来一行m+1个数字,从低到高表示G(x) 的系数。 保证输入中的系数大于等于0且小于等于9。

输出

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

样例

输入

 1 2
1 2
1 2 1

输出

1 4 5 2
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题