#include<stdio.h>
#include<stdlib.h>
#define NIL -1
typedef struct {
  int key,right,left;

} N;
void Insert(N *, int , int);
void Preorder(N *, int );
void Inorder(N *, int );
int main (){
  int i,n,key,j=0;
  char com[8];
  N *Tree;
  scanf("%d",n);
  Tree = malloc(sizeof(N)*n);

  for(i=0;i<n;i++){
    scanf("%s",com);
    if(com[0]=='i'){
    scanf("%d",&key);
    Insert(Tree,j,key);
    j++;
  }
  else if(com[0]=='p'){
    if(j>0){
      Inorder(Tree,0);
      printf("\n");

      Preorder(Tree,0);
      printf("\n");

    }
  }
}
  free(Tree);
  return 0;
}
void Insert(N *Tree,int j,int key ){
  int x=0,y;
  Tree[j].key=key;
  Tree[j].left=NIL;
  Tree[j].right=NIL;
  if(j==0){
    return ;
  }
  while( x!= NIL){
    y=x;
    if(key<Tree[x].key){
      x=Tree[x].left;

    }
    else{
      x=Tree[x].right;
    }
  }
  if(key<Tree[y].key){
    Tree[y].left=j;
  }
  else{
    Tree[y].right=j;
  }
}
void Preorder(N *Tree, int k){
  if(k==NIL){
    return;
  }
  printf(" %d",Tree[k].key);
  Preorder(Tree,Tree[k].left);
  Preorder(Tree,Tree[k].right);

}
void Inorder(N *Tree, int k){
  if(k==NIL){
    return;
  }
  printf(" %d",Tree[k].key);
  Inorder(Tree,Tree[k].left);
  Inorder(Tree,Tree[k].right);

}