1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 #include<complex> 9 using namespace std;10 #define maxn 100100011 #define llg long long 12 #define Pi acos(-1.0)13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 typedef complex<double> XU;15 16 struct FFT17 {18     llg rev[maxn],L,n,m,c[maxn];19     20     void fft(XU *z,llg f)21     {22         for (llg i=0;i<n;i++) if (i<rev[i]) swap(z[i],z[rev[i]]);23         for (llg i=1;i<n;i*=2)24         {25             XU wn(cos(Pi/i),sin(Pi/i));26             for (llg p=i*2,j=0;j<n;j+=p)27             {28                 XU w(1,0);29                 for (llg k=0;k<i;k++,w*=wn)30                 {31                     XU x=z[j+k],y=w*z[j+k+i];32                     z[j+k]=x+y,z[j+k+i]=x-y;33                 }34             }35         }36         if (f==-1) reverse(z+1,z+n);37     }38 39     XU a[maxn],b[maxn];40 41     void work()42     {43         m+=n;44         for (n=1;n<=m;n*=2) L++;45         for (llg i=0;i<n;i++) rev[i]=(rev[i/2]/2)|((i&1)<<(L-1));46         fft(a,1); fft(b,1);47         for (llg i=0;i<n;i++) a[i]=a[i]*b[i];48         fft(a,-1);49         for (llg i=0;i<=m;i++) c[i]=(llg)(a[i].real()/n+0.5);50     }51 52 }fft;53 54 llg read() {llg x; scanf("%lld",&x); return x;}55 56 int main()57 {58     yyj("fft");59     cin>>fft.n>>fft.m;60     for (llg i=0;i<=fft.n;i++) fft.a[i]=read();61     for (llg i=0;i<=fft.m;i++) fft.b[i]=read();62     fft.work();63     for (llg i=0;i<=fft.m;i++) printf("%lld ",fft.c[i]);64     return 0;65 }