#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 10000

struct Node{
  int key;
  struct Node *p;
  struct Node *r;
  struct Node *l;
};

struct Node *root,*NIL;

void Insert(int );
void inorder(struct Node *);
void preorder(struct Node *);

int main(){
  int n,i,num;
  char order[8];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",order);
    if(strcmp(order,"print")==0){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }else if(strcmp(order,"insert")==0){
      scanf("%d",&num);
      Insert(num);
      }
   }


 return 0;
}

void Insert(int k){
 struct Node *y = NIL;
 struct Node *x = root;
 struct Node *z;

 z=(struct Node *)malloc(sizeof(struct Node));
 z->key=k;
 z->l=NIL;
 z->r=NIL;

 while(x!=NIL){
   y=x;
   if(z->key < x->key){
     x=x->l;
   }else{
     x=x->r;
   }
 }

z->p=y;
if(y==NIL){
  root=z;
}else{
  if(z->key < y->key){
    y->l=z;
  }else{
    y->r=z;
  }
}
}

void inorder(struct Node *x){
  if(x!=NIL){
    inorder(x->l);
    printf(" %d",x->key);
    inorder(x->r);
  } 
}

void preorder(struct Node *x){
  if(x!=NIL){
    printf(" %d",x->key);
    preorder(x->l);
    preorder(x->r);
  }
}
