给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。

第一行包含一个正整数n(1<=n<=200000)，表示A串的长度。

第二行包含n个正整数，其中第i个数表示A[i](1<=A[i]<=1000)。

第三行包含一个正整数m(1<=m<=200000)，表示B串的长度。

第四行包含m个正整数，其中第i个数表示B[i](1<=B[i]<=1000)。

输出一行，包含n+m个正整数，即字典序最小的T串。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 400010

int len,val[maxn];

int S[maxn]; int SA[maxn];

int ws[maxn],wa[maxn],wv[maxn],wb[maxn];

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void DA(int *r,int *sa,int n,int m)

{

    int p,*x=wa,*y=wb,*t;

    for (int i=; i<m; i++) ws[i]=;

    for (int i=; i<n; i++) ws[x[i]=r[i]]++;

    for (int i=; i<m; i++) ws[i]+=ws[i-];

    for (int i=n-; i>=; i--) sa[--ws[x[i]]]=i;

    p=; for (int j=; p<n; j*=,m=p)

        {

            p=; for (int i=n-j; i<n; i++) y[p++]=i;

            for (int i=; i<n; i++) if (sa[i]>=j) y[p++]=sa[i]-j;

            for (int i=; i<n; i++) wv[i]=x[y[i]];

            for (int i=; i<m; i++) ws[i]=;

            for (int i=; i<n; i++) ws[wv[i]]++;

            for (int i=; i<m; i++) ws[i]+=ws[i-];

            for (int i=n-; i>=; i--) sa[--ws[wv[i]]]=y[i];

            t=x; x=y; y=t; p=; x[sa[]]=;

            for (int i=; i<n; i++)

                x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

        }

}

int rank[maxn],height[maxn];

void calheight(int *r,int *sa,int n)

{

    int k=;

    for (int i=; i<=n; i++) rank[sa[i]]=i;

    for (int i=; i<n; height[rank[i++]]=k)

        {k?k--:;for (int j=sa[rank[i]-]; r[i+k]==r[j+k]; k++);}

}

int N,M;

int main()

{

    N=read();

    for (int i=; i<N; i++) S[i]=read(); S[N]=;

    M=read();

    for (int i=; i<=M; i++) S[i+N]=read(); S[N+M+]=;

    DA(S,SA,N+M+,); calheight(S,SA,N+M+);

    int a=,b=N+;

    for (int i=; i<=N+M; i++)

        {

            if (i==N) continue;

            if (a==N) {for (int j=b; j<=N+M; j++) printf("%d ",S[j]); break;}

            if (b==N+M+) {for (int j=a; j<N; j++) printf("%d ",S[j]); break;}

            if (rank[a]<rank[b]) printf("%d ",S[a]),a++;

                else printf("%d ",S[b]),b++;

        }

    return ;

}