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

struct node{
  int key;
  struct node *p,*r,*l;
};
struct node *rt;
void insert(int);
void in(struct node *);
void pre(struct node *);
int main(){
  int m,i,x;
  char c[7];
  
  scanf("%d",&m);
  i=0;
  while(i<m){
    scanf("%s",c);
    if(c[0]=='i'){
       scanf("%d",&x);
       insert(x);
    }
    else if(c[0]=='p'){
      in(rt);
      printf("\n");
      pre(rt);
      printf("\n");
    }
    i++;
  }
  return 0;
}

void insert(int k){
  struct node *y=NULL, *x=rt,*z;
  
  z=(struct node *)malloc(sizeof(struct node));
  z->key=k; z->l=NULL; z->r=NULL;
  while(x!=NULL){
    y=x;
    if(z->key < x->key)x=x->l;
    else x=x->r;
  }
    z->p=y;
    
    if(y==NULL)rt=z;
    else {
      if(z->key < y->key) y->l=z;
      else y->r=z;
    }
    
  }

void in(struct node *p){
 
  if(p==NULL) return 0;
   in(p->l);
   printf(" %d",p->key);
   in(p->r);
}

void pre(struct node *p){
 
  if(p==NULL) return 0;
  printf(" %d",p->key);
  pre(p->l);
  pre(p->r);
}



