#include<cstdio>
#include<cstring>
#include<cmath>
#define re register
#define ui unsigned int
#define ull unsigned long long
const double pi=3.14159265358979323846264338327950;
struct com
{
float a,b;
inline com operator +(const com&A){return(com){a+A.a,b+A.b};}
inline void operator +=(const com&A){a+=A.a,b+=A.b;}
inline com operator -(const com&A){return(com){a-A.a,b-A.b};}
inline com operator *(const com&A){return(com){a*A.a-b*A.b,a*A.b+b*A.a};}
inline com operator *(re const double &o) {return (com){a*o,b*o};}
inline com operator /(const int&A){return(com){a/A,b/A};}
inline com operator !(){return(com){a,-b};}
inline bool operator !=(const com&A){return a!=A.a||b!=A.b;}
};
inline com ar(re const com&A){return(com){-A.b,A.a};}
inline com af(re const com&A){return(com){A.b,-A.a};}
int getlen(re int n){re int x=1;for(n--;n;n>>=1,x<<=1);return x;}
unsigned int rev[(1<<21)+1];
com w[(1<<21)+1];
void init(re int len)
{
re int x=len>>1;
for(re int i=1;i<len;i++)
rev[i]=(i&1)?((rev[i>>1]>>1)|x):(rev[i>>1]>>1);
w[0]=w[1]=(com){1,0};
for(re int i=2;i<=18;++i) {
com g=(com){cos(2*pi/(1<<i)),sin(2*pi/(1<<i))};
for(re int j=1<<i-1;j<1<<i;++j) w[j]=(j&1)?w[j-1]*g:w[j>>1];
}
}
void fft(re com *a,re int len,re int dft)
{
re int x,i1;
re com x1;
for(re int i=0;i<len;i++)if(i<(x=rev[i]))x1=a[i],a[i]=a[x],a[x]=x1;
for(re int i=2;i<=len;i<<=1)
{
i1=i>>1;
re com g=(com){cos(2*pi/i),dft*sin(2*pi/i)};
w[0]=(com){1,0};
for(re int k=i1-2;k>0;k-=2)w[k]=w[k>>1];
for(re int k=1;k<i1;k+=2)w[k]=w[k-1]*g;
for(re int j=0;j<len;j+=i)
{
for(re com*A=a+j,*A1=A+i1,*W=w,*A2=A1;A!=A2;A++,A1++,W++)
{
re com y;
y.a=(*A1).a*(*W).a-(*A1).b*(*W).b;
y.b=(*A1).a*(*W).b+(*A1).b*(*W).a;
(*A1).a=(*A).a-y.a;
(*A1).b=(*A).b-y.b;
(*A).a+=y.a;
(*A).b+=y.b;
}
}
}if(dft==-1)for(re int i=0;i<len;i++)a[i]=a[i]/len;
}
void DFT(ui *a,com *R1,int n,int len) {
for(re int i=0;i<n+1>>1;++i) R1[i]=(com){a[i<<1],a[i<<1|1]};
fft(R1,len,1);
}
com T1[(1<<20)+1];
void DFTMul(com *R1,com *S1,int len) {
for(re int i=0;i<len;++i) {
re int j=len-1&len-i;
com tmp=(i&len>>1)?(com){1,0}-w[i^len>>1]:w[i]+(com){1,0};
T1[i]=(R1[i]*S1[i]*4-(R1[i]-!R1[j])*(S1[i]-!S1[j])*tmp)*0.25;
}
}
void IDFT(ui *__ans,int r,int len) {
fft(T1,len,-1);
for(re int i=0;i<r;++i) __ans[i]=(i&1)?(ull)(T1[i>>1].b+0.5):(ull)(T1[i>>1].a+0.5);
}
ui x1[(1<<21)+1],x2[(1<<21)+1];
com xx1[(1<<21)+1],xx2[(1<<21)+1];
void poly_multiply(re unsigned *a,re int n,re unsigned *b,re int m,re unsigned *c)
{
re int len=getlen(n-1),x;
re unsigned int ans=0;
init(len);
DFT(a,xx1,n-1,len);DFT(b,xx2,n+1,len);
DFTMul(xx1,xx2,len);
IDFT(c,len<<1,len);
}