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

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

struct Node *root, *NIL;

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

int main(){
  int str1 = 0, str2 = 0;
  int i,n,key;
  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",&key);
      Insert(key);
      str1 = 0;
    }
    else if(str2 == 1){
      str2 = 0;
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }
  }

  return 0;
}

void Insert(int n){
struct  Node *parent = root;
struct  Node *q = NIL;
struct  Node *right;

 right = (struct Node *)malloc(sizeof(struct Node));
 right -> k = n;
 right -> l = NIL;
 right -> r = NIL;
 
 while(parent != NIL){
   q = parent;
   if(right->k < parent->k){
     parent = parent -> l;
   }
   else{
     parent = parent -> r;
   }
 }
 
 right -> p = q;
  if(q == NIL){
    root = right;
  }
  else{
    if(right->k < q->k){
      q -> l = right;
    }
    else{
      q -> r = right;
    }
  }
}

void Inorder(struct Node *x){
  if(x == NIL) return;
  Inorder(x -> l);
  printf(" %d",x -> k);
  Inorder(x -> r);
}

void Preorder(struct Node *x){
  if(x == NIL) return;
  printf(" %d",x -> k);
  Preorder(x -> l);
  Preorder(x -> r);
}


