#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define L 20
#define Gard NULL

struct Tree{
  int nodekey;
  struct Tree *parent;
  struct Tree *leftch;
  struct Tree *rightch;
};

typedef struct Tree  *Search;

void Pre(Search );
void In(Search );


int main(){
  int loop,numnode;
  char order[L];
  int i;
  Search road;
  Search x,y,z;
    
  scanf("%d",&loop);
  
  for(i=0;i<loop;i++){
    scanf("%s",order);
    
    if(order[0]=='i'){
      scanf("%d",&numnode);
      x=road;
      y=Gard;
      z=malloc(sizeof(struct Tree));
      z->nodekey=numnode;
      z->leftch=Gard;
      z->rightch=Gard;
  
      while(x!=Gard){
	y=x;
    
	if(z->nodekey<x->nodekey){
	  x=x->leftch;
	}
    
	else{
	  x=x->rightch;
	}
      }
  
      z->parent=y;
  
      if(y==Gard){
	road=z;
      }
  
      else if(z->nodekey<y->nodekey){
	y->leftch=z;
      }
  
      else{
	y->rightch=z;
      }
    }
    
    if(order[0]=='p'){
      In(road);
      printf("\n");
      Pre(road);
      printf("\n");
    }
  }
  
  return 0;
}

void Pre(Search road){

  if(road==Gard){
    return;
  }
  
  printf(" %d",road->nodekey);
 
  Pre(road->leftch);
  Pre(road->rightch);
  
}

void In(Search road){

  if(road==Gard){
    return;
  }
  
  In(road->leftch);
  
  printf(" %d",road->nodekey);
  
  In(road->rightch);
}

