#include<stdio.h>
#define MAX 500001

 struct Node{
           int key;
           int parent,left,right;
           };

 struct Node T[MAX+1];
 int NIL=-1;
 int root;
 int ix=0;

 int insert(int k){
               int x,y,z;
               x=root;
               y=NIL;
               z=ix++;

               T[z].key=k;
               T[z].right=NIL;
               T[z].left=NIL;

               while(x != NIL){
                           y=x;
                           if(T[z].key<T[y].key){x=T[y].left;}
                           else {x=T[y].right;}
                           }
               T[z].parent=y;
               if(y==NIL){root=z;}
               else {
                     if(T[z].key<T[y].key){T[y].left=z;}
                     else {T[y].right=z;}
                     }
               }

 int preorder(int u){
               if(u==NIL)return;
               printf(" %d",T[u]);
               preorder(T[u].left);
               preorder(T[u].right);
               }

 int inorder(int u){
               if(u==NIL)return;
               inorder(T[u].left);
               printf(" %d",T[u]);
               inorder(T[u].right);
               }


 int main(){
       int i,m,k;
       root=NIL;
       char com[10];
       scanf("%d",&m);
       for(i=0;i<m;i++){
                  scanf("%s",&com);
                  if(com[0]=='i'){
                                 scanf("%d",&k);
                                 insert(k);
                                 }
                  else if(com[0]=='p'){
                                inorder(root);
                                printf("\n");
                                preorder(root);
                                printf("\n");
                                }
                  }
       return 0;
       }
