#include<stdio.h>
#define MAX 500001
#define NIL -1
typedef struct node{
  int left;
  int right;
  int key;
  int p;

}Node;
Node node[MAX];
int root=NIL;
void inorder(int);
void preorder(int);
void addTree(int n){
  int tmp;
  //rootが空の場合
  if(node[n].key==root){
    root=n;
    node[root].key=n;
    
  }
  else{
  tmp=node[root].key;
  while(1){
    if(node[tmp].key>n){
      if(node[tmp].left!=NIL){
	tmp=node[tmp].left;
      }
      else{
	node[tmp].left=n;
	node[node[tmp].left].key=n;
	break;
      }
    }
    else{
      if(node[tmp].right!=NIL){
	tmp=node[tmp].right;
	
      }
      else{
	node[tmp].right=n;
	node[node[tmp].right].key=n;
	break;
      }
    }
  }
  
  node[n].p=tmp;
  
  }
}
int main(){
  int num,i,n,l,tmp,r;
  char name[100];
  scanf("%d",&n);
 for(i=0;i<MAX;i++){//初期化
    node[i].p=NIL;
    node[i].left=NIL;
    node[i].right=NIL;
    node[i].key=NIL;
    
  }


 for(i=0;i<n;i++){
    scanf("%s",name);
    if(name[0]=='i'){
      scanf("%d",&num);
      addTree(num);
      }
      
   else if(name[0]=='p'){
      tmp=i;
      break;
    }
  }
 
 
  inorder(root);
   printf("\n");
   preorder(root);
   printf("\n");

  return 0;
}
void inorder(int t){
  if(node[t].left!=NIL){
    inorder(node[t].left);
  }
    printf(" %d",node[t].key);
  if(node[t].right!=NIL){
    inorder(node[t].right);
  }
}
void preorder(int t){
 
      printf(" %d",node[t].key);
  if(node[t].left!=NIL){
    preorder(node[t].left);
  }
  if(node[t].right!=NIL){
    preorder(node[t].right);
  }
}


