#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define pi 3.14159265358979323846
struct C
{
double x,y;
C operator+(const C b)const{return {x+b.x,y+b.y};}
C operator-(const C b)const{return {x-b.x,y-b.y};}
C operator*(const C b)const{return {x*b.x-y*b.y,x*b.y+y*b.x};}
};
const int _lg2[]={0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3};
using namespace std;
int tmp1,n,m,N;
int lg2(int i)
{
int tmp(0);
if(i>65535)tmp|=16,i>>=16;
if(i>255)tmp|=8,i>>=8;
if(i>15)tmp|=4,i>>=4;
return tmp+_lg2[i];
}
double co[23],si[23];
void fft(C*a,int n)
{
if(n==1)return;
int mid=n>>1;
C x__={1,0},x_={co[lg2(n)],si[lg2(n)]};
fft(a,mid),fft(a+mid,mid);
for(int i=0;i<mid;i++,x__=x__*x_)
{
C x(a[i+mid]*(C){x__.x,x__.y});
a[i+mid]=a[i]-x,a[i]=a[i]+x;
}
}
void ifft(C*a,int n)
{
if(n==1)return;
int mid=n>>1;
C x__={1,0},x_={co[lg2(n)],si[lg2(n)]};
ifft(a,mid),ifft(a+mid,mid);
for(int i=0;i<mid;i++,x__=x__*x_)
{
C x(a[i+mid]*(C){x__.x,-x__.y});
a[i+mid]=a[i]-x,a[i]=a[i]+x;
}
}
C a[1<<21];
int r[1<<21];
void rev(C*a,int n){for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);}
void poly_multiply(unsigned *_a, int n, unsigned *_b, int m, unsigned *_c)
{
for(int i=0;i<=22;i++)co[i]=cos(2*pi/(1<<i)),si[i]=sin(2*pi/(1<<i));
int l_n(0);
++n,m=n,N=1<<21;
for(int i=0;i<N;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l_n-1));
for(int i=0;i<n;i++)a[i].x=_a[i],a[i].y=_b[i];
rev(a,N);
fft(a,N);
for(int i=0;i<N;i++)a[i]=a[i]*a[i];
rev(a,N);
ifft(a,N);
for(int i=0;i<n+m-1;i++){_c[i]=round(a[i].y/N/2);}
}