/* Code by pp_orange */ #include<bits/stdc++.h> #define m_p(a,b) make_pair(a,b) #define pb push_back #define ll long long #define ull unsigned long long #define lld long double #define inf 0x7FFFFFFF #define inff 9223372036854775807 #define rep(i,l,r) for(int i=l;i<r;++i) #define repp(i,l,r) for(int i=l;i<=r;++i) #define per(i,r,l) for(int i=r-1;i>=l;--i) #define pper(i,r,l) for(int i=r;i>=l;--i) #define pii pair<int,int> #define fi first #define se second #define p_q priority_queue #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define ls(x) ((x)<<1) #define rs(x) ((x)<<1|1) #define lb(x) ((x)&-(x)) const int mod = 998244353; //#define int ll using namespace std; inline int rd(){ int x(0),f(1);char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*f; } inline void out(int X){ if(X<0) {X=~(X-1); putchar('-');} if(X>9) out(X/10); putchar(X%10+'0'); } ll pw(ll x,int d){ ll t = 1; for(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod; return t; } #define MAX (1<<21) namespace poly{ const int de = 1; const int intsz = sizeof(int); int getN(int n){ int N = 1; while(N<=n)N<<=1; return N; } namespace polyNTT{ int r[MAX]; int nwsz = -1; void initR(int N,int lim){ if(nwsz==lim)return ; nwsz = lim; rep(i,1,N)r[i] = (r[i>>1]>>1)|((i&1)<<(lim-1)); return ; } const int G = 3; const int Gi = pw(G,mod-2); int x,y; void NTT(int *a,int N,int tp){ //1:G, -1:Gi //need init R if(de)assert(__builtin_ctz(N)==nwsz); const int g = tp==1?G:Gi; int omg; ll w; rep(i,0,N)if(r[i]<i)swap(a[i],a[r[i]]); for(int mid=1;mid<N;(mid<<=1)){ omg = pw(g,(mod-1)/(mid<<1)); for(int i=0,len=(mid<<1);i<N;i+=len){ w = 1; for(int j=i;j<i+mid;++j,w=w*omg%mod){ x = a[j]; y = a[j+mid]*w%mod; a[j] = (x+y)%mod; a[j+mid] = (x-y+mod)%mod; } } } return ; } }using polyNTT::NTT,polyNTT::initR; namespace polyMul{ int tmp[MAX]; void Mul(int *a,int n,int *b,int m){ //Mul(rlt,n,b,m) , won't destroy b //a^n and b^m memcpy(tmp,b,intsz*(m+1)); int lim = 0; int N = 1; while(N<=n+m){ N <<= 1; lim++; } initR(N,lim); NTT(a,N,1); NTT(b,N,1); ll Ni = pw(N,mod-2); rep(i,0,N)a[i] = (ll)a[i]*b[i]%mod*Ni%mod; NTT(a,N,-1); memcpy(b,tmp,intsz*(m+1)); memset(b+m+1,0,intsz*(N-(m+1))); return ; } }using polyMul::Mul; namespace polyInv{ int f[MAX]; void Inv(int *b,int *a,int n){ //Inv(output,input,n) mod x^n , won't destroy a int N = 1; int lim = 0; b[0] = pw(a[0],mod-2);b[1] = 0; while(N<n){ lim++; N <<= 1; initR(N,lim); memset(b+N,0,intsz*N); memcpy(f,a,intsz*N); memset(f+N,0,intsz*N); initR(N<<1,lim+1); NTT(b,N*2,1); NTT(f,N*2,1); rep(i,0,N*2)f[i] = b[i]*(2-(ll)b[i]*f[i]%mod+mod)%mod; NTT(f,N*2,-1); ll Ni = pw(N*2,mod-2); rep(i,0,N)b[i] = f[i]*Ni%mod; memset(b+N,0,intsz*N); } memset(b+n,0,intsz*(N-n)); } }using polyInv::Inv; namespace polySqrt{ int gi[MAX]; int f[MAX]; const int inv2 = pw(2,mod-2); void Sqrt(int *b,int *a,int n){ //Sqrt(output,input,n) , mod x^n int N = 1; int lim = 0; if(de)assert(a[0]==1); b[0] = 1;b[1] = 0; while(N<n){ lim++; N <<= 1; memset(b+N,0,intsz*N); Inv(gi,b,N); memset(gi+N,0,intsz*N); memcpy(f,a,intsz*N); memset(f+N,0,intsz*N); initR(N*2,lim+1); NTT(gi,N*2,1); NTT(f,N*2,1); NTT(b,N*2,1); ll Ni = pw(N*2,mod-2); rep(i,0,N*2)b[i] = ((ll)f[i]*gi[i]%mod+b[i])*inv2%mod*Ni%mod; NTT(b,N*2,-1); memset(b+N,0,intsz*N); } memset(b+n,0,intsz*(N-n)); return ; } }using polySqrt::Sqrt; void Dev(int *a,int n){ //get Dev [ 0 , n ) rep(i,0,n-1)a[i] = ((ll)a[i+1]*(i+1))%mod; a[n-1] = 0; return ; } namespace polyInter{ int inv[MAX] = {0,1}; int invsz = 1; void initInv(int sz){ if(sz<=invsz)return ; repp(i,2,sz)inv[i] = (mod-(ll)inv[mod%i]*(mod/i)%mod); invsz = sz; } void Inter(int *a,int n){ //get Inter [ 0 , n ) initInv(n); per(i,n,1)a[i] = ((ll)a[i-1]*inv[i])%mod; a[0] = 0; return ; } }using polyInter::Inter; namespace polyLn{ int tmp[MAX]; void Ln(int *b,int *a,int n){ //Ln(out,in,n) , won't destroy a , mod x^n memcpy(tmp,a,intsz*n); int N = getN(n-1)*2; if(de)assert(a[0]==1); memcpy(b,a,intsz*N); Inv(a,b,n); Dev(b,n); initR(N,__builtin_ctz(N)); NTT(a,N,1); NTT(b,N,1); ll Ni = pw(N,mod-2); rep(i,0,N)b[i] = ((ll)a[i]*b[i]%mod*Ni)%mod; NTT(b,N,-1); memset(b+n,0,intsz*(N-n)); Inter(b,n); memcpy(a,tmp,intsz*n); memset(a+n,0,intsz*(N-n)); return ; } }using polyLn::Ln; namespace polyExp{ int c[MAX]; int d[MAX]; void Exp(int *b,int *a,int n){ //Exp(out,in,n) , won't destroy a // mod x^n if(de)assert(a[0]==0); int N = 1,lim = 0; b[0] = 1,b[1] = 0; while(N<n){ N <<= 1; lim++; memset(b+N,0,intsz*N); Ln(c,b,N); memcpy(d,a,intsz*N); memset(d+N,0,intsz*N); initR(N*2,lim+1); NTT(b,N*2,1); NTT(c,N*2,1); NTT(d,N*2,1); ll Ni = pw(N*2,mod-2); rep(i,0,N*2)b[i] = (1ll-c[i]+d[i]+mod)%mod*b[i]%mod*Ni%mod; NTT(b,N*2,-1); memset(b+N,0,intsz*N); } memset(b+n,0,intsz*(N-n)); return ; } }using polyExp::Exp; namespace polyPow{ //暂不支持多测 int tmp[MAX]; int c[MAX]; void Pow(int *b,int *a,int n,ll d){ if(d==0){ memset(b,0,intsz*n); b[0] = 1; return ; } //Pow(rlt&input,len,times); mod x^len if(de)assert(a[0]==1); Ln(tmp,a,n); rep(i,0,n)tmp[i] = (tmp[i]*d)%mod; Exp(b,tmp,n); return ; } void exPow(int *b,int *a,int n,ll d,ll d2 = -1){ //exPow(rlt&input,len,times%mod,times%(mod-1)); mod x^len if(d2==-1)d2=d; if(d==0){ memset(b,0,intsz*n); b[0] = pw(a[0],d2); return ; } int cnt = 0; rep(i,0,n){ if(a[i]==0)cnt++; else break; } ll m = cnt*d; if(m>=n){ memset(b,0,intsz*n); return ; } ll f0 = a[cnt]; ll if0 = pw(f0,mod-2); memcpy(c,a+cnt,intsz*(n-m)); rep(i,0,n-m)c[i] = (c[i]*if0)%mod; Pow(b+m,c,n-m,d); memset(b,0,intsz*m); f0 = pw(f0,d2); rep(i,m,n)b[i] = (b[i]*f0)%mod; return ; } }using polyPow::Pow,polyPow::exPow; void Rev(int *a,int n){ reverse(a,a+n+1); return ; } namespace polyDiv{ //暂不支持多测 int gi[MAX]; int tmpg[MAX]; void Div(int *q,int *r,int *f,int n,int *g,int m){ //f = q*g+r , f^n , g^m assert(m<=n); Rev(f,n);Rev(g,m); int sz = n-m+1; memcpy(tmpg,g,intsz*sz); Inv(gi,tmpg,sz); Mul(gi,sz-1,f,n); memcpy(q,gi,intsz*sz); Rev(f,n);Rev(g,m);Rev(q,n-m); //memset(q)... memcpy(tmpg,q,intsz*sz); Mul(tmpg,n-m,g,m); rep(i,0,m)r[i] = (f[i]-tmpg[i]+mod)%mod; return ; } }using polyDiv::Div; } int f[MAX],g[MAX],q[MAX],r[MAX]; signed main(){ //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); int n = rd(); int m = rd(); repp(i,0,n)f[i] = rd(); repp(i,0,m)g[i] = rd(); poly::Div(q,r,f,n,g,m); repp(i,0,n-m)cout<<q[i]<<' ';cout<<endl; rep(i,0,m)cout<<r[i]<<' ';cout<<endl; return 0; }