#include<stdio.h>
#include <stdlib.h>
typedef struct node{
  struct node *r;
  struct node *l;
  struct node *parent;
  int key;
}node;
typedef struct node * Node;

int pre(Node);

int mid(Node);

Node nose(int);

int in(Node,int);

void freedom(Node);

int main(){
  int j,n,i,ndnm;
  char b[7];
  Node first,now;
  scanf("%d",&n);
  scanf("%s %d",b,&ndnm);
  first = nose(ndnm);
  for(i=0;i<n-1;i++){
    scanf("%s",b);
    if(b[0]=='i'){
      scanf("%d",&ndnm);
      in(first,ndnm);
    }else{
      mid(first);
      printf("\n");
      pre(first);
      printf("\n");
    }
  }
freedom(first);

}
int in(Node now,int ndnm){
  while(1){
//printf("now =%d ",now->key);
    if(ndnm >= now->key){
      if(now->r != NULL)
	now = now->r;
      else{
	now->r=nose(ndnm);
	break;
      }
    }else{
      if(now->l != NULL)
	now = now->l;
      else{
	now->l=nose(ndnm);
	break;
      }
    }
  }
return 0;
}
Node nose(int key){

Node set;
set =(Node)malloc(sizeof(node));
  set->key=key;
  set->r=NULL;
  set->l=NULL;
  return set;
}

int mid(Node a){
  if(a->l != NULL)
    mid(a->l);
  printf(" ");
  printf("%d",a->key);
  if(a->r !=NULL)
    mid(a->r);
  return 0;
}


int pre(Node a){
  printf(" ");
  printf("%d",a->key);
  if(a->l != NULL)
    pre(a->l);
  if(a->r !=NULL)
    pre(a->r);
  return 0;
}

void freedom(Node a){
  if(a->l != NULL)
    free(a->l);
  if(a->r !=NULL)
    free(a->r);
free(a);
}


