#include<iostream>
#include<cstring>
using namespace std;
#define ok 1
#define error -1
int a[1000];
typedef struct BiTNode{
    int data;
    struct BiTNode * lchild, * rchild;
    BiTNode():data(-1),lchild(NULL),rchild(NULL){}
}BiTNode, *BiTree;
/***
 * T 指向排序二叉树的根
 * key 为要查找的元素
 * 若查找成功，P指向该元素的节点，并返回ok
 * 若查找失败，p指向查找路径上方问的最后一个节点，
 * 并返回false，指针f指向T的双亲，其初始调用职位NULL
 * */
int SearchBST(BiTree T, int key, BiTree f, BiTree *p){
    if(!T){
        *p = f;
        return error;
    }
    else if( T->data == key ){
        *p = T;
        return ok;
    }
    else if( key < T->data ){
        SearchBST(T->lchild, key, T, p);
    }
    else if( key>T->data){
        SearchBST(T->rchild, key, T, p);
    }
}
int insert(BiTree *T, int e){
    BiTree p = NULL;
    if( SearchBST(*T,e,NULL, &p)==error ){
        BiTree s = new BiTNode;
        s->data = e;
        if(!p){
            *T = s;
        }else if( e<p->data ){
            p->lchild = s;
        }else if( e>p->data ){
            p->rchild = s;
        }
        return ok;
    }
    return error;
}
void midOrder(BiTree T){
    if(!T){
        return ;
    }
    // cout<<"1"<<endl;
    midOrder(T->lchild);
    cout<<T->data<<' ';
    midOrder(T->rchild);
}
int Delete(BiTree *p){
    BiTree q,s;
    if(!(*p)->lchild && !(*p)->rchild ){
        *p = NULL;
    }else if( !(*p)->lchild ){
        //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；
        q = *p;
        *p = (*p)->rchild;
        delete q;
    }else if( !(*p)->rchild ){
        //右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；
        q = *p;
        *p = (*p)->lchild;
        delete q;
    }else{
        // 都不空
        q = *p;
        s = (*p)->lchild;
        while(s->rchild){
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data;
        if( q != *p ){
            q->rchild = s->lchild;
        }else{
            q->lchild = s->lchild;
        }
        delete s;
    }
    return ok;
}
int DELBST(BiTree *T, int key){
    if(!(*T)){
        return error;
    }
    if( key== (*T)->data ){
        Delete (T);
        return ok;
    }else if( key < (*T)->data ){
        DELBST((&(*T)->lchild), key);
    }else{
        DELBST((&(*T)->rchild), key);
    }
}
int main(){
   int t;
   cin>>t;
   while(t--){
       memset(a,0,sizeof(a));
       int len;
       cin>>len;
       BiTree T = NULL;
       for(int i=0; i<len; i++){
           cin>>a[i];
           insert(&T,a[i]);
       }
       midOrder(T);
       cout<<endl;
      int op;
      cin>>op;
      while(op--){
          int temp;
          cin>>temp;
          insert(&T, temp );
        // DELBST(&T,temp);
          midOrder(T);
          cout<<endl;
      }
   }
   return 0;
}