const int M=100005,N=2*1234;struct edge{    int to,next,cap;}e[M];int cnt=1,last[N],h[N];void insert(int a,int b,int c){    e[++cnt]=(edge){b,last[a],c};last[a]=cnt;    e[++cnt]=(edge){a,last[b],c};last[b]=cnt; }bool bfs(int s,int t){    memset(h,-1,sizeof(h));    queue<int>q;    q.push(s);h[s]=0;    while(!q.empty()){        int c=q.front();q.pop();        for(int i=last[c];i;i=e[i].next){            if(e[i].cap&&h[e[i].to]==-1){                h[e[i].to]=h[c]+1;                q.push(e[i].to);            }        }    }    return h[t]^(-1);}int dfs(int x,int t,int f){    if(x==t)return f;    int used=0,w=0;    for(int i=last[x];i;i=e[i].next){        if(h[e[i].to]==h[x]+1){            w=dfs(e[i].to,t,min(f-used,e[i].cap));            e[i].cap-=w;            e[i^1].cap+=w;            used+=w;            if(used==f)                return f;        }    }    if(!used)h[x]=-1;    return used;}int dinic(int s,int t){    int ans=0;    while(bfs(s,t)){        int flow=dfs(s,t,inf);        ans+=flow;        if(ans>=inf)return ans;     }    return ans;}

struct cpx {    double r,i;    cpx(double real=0.0,double image=0.0) {r=real;i=image;}    cpx operator +(const cpx w) {return cpx(r+w.r,i+w.i);}    cpx operator -(const cpx w) {return cpx(r-w.r,i-w.i);}    cpx operator *(const cpx w) {return cpx(r*w.r-i*w.i,r*w.i+i*w.r);}};cpx a[N],b[N];cpx epsilon[N],arti_epsilon[N];void init_epsilon(int n){    double pi=acos(-1);    for(int i=0;i!=n;i++){        epsilon[i]=cpx(cos(2.0*pi*i/n),sin(2.0*pi*i/n));         //arti_epsilon[i]=conj(epsilon[i]);        arti_epsilon[i]=cpx(cos(2.0*pi*i/n),-sin(2.0*pi*i/n));    }}void rev(int n,cpx*t){    for(int i=0,j=0;i!=n;i++){        if(i>j)swap(t[i],t[j]);        for(int l=n/2;(j^=l)<l;l>>=1);    }}void dft(int n,cpx*x,cpx*w){    rev(n,x);    for(int i=2;i<=n;i<<=1){        int m=i/2;        for(int j=0;j<n;j+=i){            for(int k=0;k!=m;k++){                cpx t=x[j+m+k]*w[n/i*k];                x[j+m+k]=x[j+k]-t;                x[j+k]=x[j+k]+t;            }        }    }}cpx c[N]; void mul(cpx *a,cpx *b){    int A,B;    A=gi;B=gi;++A,++B;    for(int i=0;i<A;i++)a[i].r=gi;    for(int i=0;i<B;i++)b[i].r=gi;    int t=max(A,B);    int n=1;    for(;n<t*2;n<<=1);    init_epsilon(n);    dft(n,a,epsilon);    dft(n,b,epsilon);    // py trade    for(int i=0;i<n;i++)c[i]=a[i]*b[i];    int nn=n;cout<<n;    dft(n,c,arti_epsilon);    for(int i=0;i<=A+B-1;i++)printf("%d ",(int)(c[i].r/nn+0.5));}

namespace slpf{    #define N 123456    #define M 223456    struct edge{        int to,next;    }e[M];int rt,cnt,last[N],top[N],siz[N],dep[N],fa[N],son[N],id[N],hp[N],idcnt=0,hpcnt=0;    void insert(int a,int b){        e[++cnt]=(edge){b,last[a]};        last[a]=cnt;    }    void dfs1(int x){        siz[x]=1;        for(int i=last[x];i;i=e[i].next){            int j=e[i].to;    //        fa[j]=x;            dep[j]=dep[x]+1;            dfs1(j);            if(siz[j]>siz[son[x]])son[x]=j;        }    }    void dfs2(int x,int t){        top[x]=t;id[++idcnt]=x;hp[x]=idcnt;        if(son[x])dfs2(son[x],t);        for(int i=last[x];i;i=e[i].next)            if(e[i].to!=son[x])dfs2(e[i].to,e[i].to);            }    int tiao(int x,int d){        for(;fa[top[x]]&&dep[fa[top[x]]]>=d;x=fa[top[x]]);        return id[hp[x]-dep[x]+d];    }    int lca(int a,int b){        int f1=top[a],f2=top[b];        while(f1!=f2){            if(dep[f1]<dep[f2])            swap(f1,f2),swap(a,b);            a=fa[f1];            f1=top[a];        }        return dep[a]>dep[b]?b:a;    }    void debug(){        memset(dep,0,sizeof(dep));idcnt=0;        memset(last,0,sizeof(last));cnt=0;        memset(son,0,sizeof(son));memset(fa,0,sizeof(fa));        memset(siz,0,sizeof(siz));        int n=gi;        for(int i=1;i<n;i++){            int a=gi,b=gi;            insert(a,b);            fa[b]=a;        }         int rat=1;        while(fa[rat])rat=fa[rat];        rt=rat;        dfs1(rt);        dfs2(rt,rt);    printf("%d\n",lca(gi,gi));    };}

const double eps=1e-8;int cmp(double x){    if(fabs(x)<eps)return 0;    if(x>0)return 1;    return -1;} struct point{    double x,y;    point(){    }    point(double a,double b):x(a),y(b){}    void input(){        scanf("%lf%lf",&x,&y);    }    friend point operator+(point a,point b){return point(a.x+b.x,a.y+b.y);}    friend point operator-(point a,point b){return point(a.x-b.x,a.y-b.y);}    friend point operator*(point a,double b){return point(a.x*b,a.y*b);}    friend point operator*(double a,point b){return point(a*b.x,a*b.y);}     friend bool operator==(point a,point b){return !cmp(a.x-b.x)&&!cmp(a.y-b.y);}    double norm(){return sqrt(x*x+y*y);}};double det(point a,point b){return a.x*b.y-a.y*b.x;}double dot(point a,point b){return a.x*b.x+a.y*b.y;}double dist(point a,point b){return (a-b).norm();}struct line{    point a,b;    line(point x,point y):a(x),b(y){}};struct convex{    vector<point>P;    convex(int Size=0){P.resize(Size);} };bool lss(point a,point b){    return cmp(a.x-b.x<0)||(cmp(a.x-b.x)==0&&cmp(a.y-b.y)<0); }// checked by poj 1113convex Graham(vector<point> a){    convex res(2*a.size()+5);    sort(a.begin(),a.end(),lss);    a.erase(unique(a.begin(),a.end()),a.end());    int m=0;    for(int i=0;i<a.size();i++){        while(m>1&&cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m;        res.P[m++]=a[i];    }    int k=m;//上凸壳大小     for(int i=a.size()-2;i>=0;i--){        while(m>k&&cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m;        res.P[m++]=a[i];    }    res.P.resize(m-(a.size()>1));    return res;}void debug(){    int n,L;    n=gi;    vector<point>a(n);    for(int i=0;i<a.size();i++){        a[i].input();    }}

#define N 400005struct Suffix_Array{    int s[N],sa[N],rk[N],SA[N],RK[N],v[N],h[N],len;    int mn[N][19],lg[N];    void mul(int k,int *sa,int *rk,int *SA,int *RK){        for(int i=1;i<=len;i++) v[rk[sa[i]]]=i;        for(int i=len;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;        for(int i=len-k+1;i<=len;i++) SA[v[rk[i]]--]=i;        for(int i=1;i<=len;i++)             RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);    }    void get_sa(int lim){        for(int i=1;i<=len;i++) v[s[i]]++;        for(int i=1;i<=lim;i++) v[i]+=v[i-1];        for(int i=1;i<=len;i++) sa[v[s[i]]--]=i;        for(int i=1;i<=len;i++) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i-1]]!=s[sa[i]]);        for(int k=1;k<=len;k<<=1) {            mul(k,sa,rk,SA,RK);;            memcpy(sa,SA,len+1<<2);            memcpy(rk,RK,len+1<<2);        }        for(int k=0,j,i=1;i<=len;i++){            j=sa[rk[i]-1];            while(s[j+k]==s[i+k]) k++;            h[rk[i]]=k;if(k) k--;        }        for(int i=1;i<=len;i++) mn[i][0]=h[i];        for(int j=1;(1<<j)<=len;j++) {            for(int i=1;i+(1<<j)-1<=len;i++)                mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);        }        for(int i=2;i<=len;i++) lg[i]=lg[i>>1]+1;    }    int get_mn(int l,int r){        int t=lg[r-l+1];        return min(mn[l][t],mn[r-(1<<t)+1][t]);    }    int lcp(int x,int y){        if(x>y) swap(x,y);        return get_mn(x+1,y);    }}