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

struct Node{
  int s;
  struct Node *ri;
  struct Node *le;
  struct Node *oya;
};

struct Node *root, *NIL;

void Inorder(struct Node *);
void Preorder(struct Node *);

void Insert(int a){
struct  Node *p = root;
struct  Node *q = NIL;
struct  Node *r;

 r = (struct Node *)malloc(sizeof(struct Node));
 r -> s = a;
 r -> le = NIL;
 r -> ri = NIL;


 while(p != NIL){
   q = p;
   if(r->s < p->s){
     p = p -> le;
   }
   else{
     p = p -> ri;
   }
 }

 r -> oya = q;
  if(q == NIL){
    root = r;
  }
  else{
    if(r->s < q->s){
      q -> le = r;
    }

    else{
      q -> ri = r;
    }
  }
}




int main(){
  int str1 = 0;
  int str2 = 0;
  int i,n,val;
  char c1[10], c2[10]="insert", c3[10]="print";

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    scanf("%s",c1);
    if(strcmp(c1,c2) == 0) str1 = 1;
    if(strcmp(c1,c3) == 0) str2 = 1;

    if(str1 == 1){
      scanf("%d",&val);
      Insert(val);
      str1 = 0;
    }
    else if(str2 == 1){
      str2 = 0;
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }
  }

  return 0;
}



void Inorder(struct Node *x){
  if(x == NIL) return;
  Inorder(x -> le);
  printf(" %d",x -> s);
  Inorder(x -> ri);
}


void Preorder(struct Node *x){
  if(x == NIL) return;
  printf(" %d",x -> s);
  Preorder(x -> le);
  Preorder(x -> ri);
}

