FFT

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<30)
#define LINF (1LL<<60)
#define NINF -INF
#define CL(A,I) (memset(A,I,nof(A)))
#define add(A,B) (g[A].PB(B),g[B].PB(A))
#define ADD(A,B,V) (add(A,B),v[A].PB(V),v[B].PB(V))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define REP(i, n) for (int i = 0; i < n; i++)
#define F(W) REP(i,W)
#define FF(W) REP(j,W)
#define FT(I,W) for(int k(I);k<W;++k)
#define IN(n) int n; cin >> n;
#define PR(A,X) (X?A.second:A.first)
#define MX (1<<17)
#define MD(C,B) ((C)>=0?(C)%(B):((B)-(-(C))%(B))%B)
ll tt,N,a[MX],b[MX],c[MX];
typedef std::complex<double> cpx;
void dft(const cpx *s,cpx *r,int n,const cpx &wn,cpx *h){
    if(n==1){*r=*s;return;}
    int N=n>>1,j(-2),k(-1);;
    cpx *os=h,*es=h+N,*oR=h+2*N,*eR=h+3*N;
    F(N)es[i]=s[j+=2],os[i]=s[k+=2];
    cpx w(1,0),t(wn*wn);
    dft(es,eR,N,t,h+4*N),dft(os,oR,N,t,h+4*N);
    F(N)t=w*oR[i],r[i]=eR[i]+t,r[i+N]=eR[i]-t,w=wn*w;
}
int fft(ll *f,int A,ll *s,int B,ll *r){
    static cpx ra[MX],b[MX],a[MX],rb[MX],tr[MX],wn,o[(MX)<<2];
    int N(1),h(max(A,B)*2-1),H(A+B-1);
    while(N<=h)N<<=1;
    F(N)a[i]=b[i]=ra[i]=rb[i]=tr[i]={0,0};
    F(A)a[i].real(f[i]);
    F(B)b[i].real(s[i]);
    wn={cos(2*M_PI/N),sin(2*M_PI/N)};
    dft(a,ra,N,wn,o),dft(b,rb,N,wn,o);
    F(N)tr[i]=ra[i]*rb[i];
    dft(tr,rb,N,pow(wn,-1),o);
    F(N)rb[i].real(rb[i].real()/N);
    F(H)r[i]=(ll)(rb[i].real()+0.5);
    return H;
}
int main(void){
    for(scanf("%lld",&tt);tt--;){
        scanf("%lld",&N);++N;
        F(N)scanf("%lld",a+i);
        F(N)scanf("%lld",b+i);
        ll h(fft(a,N,b,N,c));
        F(h)printf("%lld%c",c[i],i+1==h?'\n':' ');
    }
    return 0;
}