
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL
 
struct node{
  struct node *l;
  struct node *r;
  struct node *p;
  int key;
};
 
typedef struct node * Node;
Node root;

main(){
  int n, i, x;
  char str[20];

  scanf("%d",&n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s",str);
 
    if (str[0]=='i'){
      scanf("%d",&x);
      insert(x);
    } 
    else if (str[0]=='p'){
      Inorder(root);
      printf("\n");
       
      Preorder(root);
      printf("\n");
    }
  }
  return 0;
}

void insert(int k){
  Node a=NIL;
  Node b=root;
  Node new;
 
  new = malloc(sizeof(struct node));
  new->key=k;
  new->l=NIL;
  new->r=NIL;
   
  while(a!=NIL){
    b=a;
    if(new->key < a->key) a=a->l;
    else a=a->r;
  }
  new->p=b;
   
  if(b==NIL) root=new;
  else if(new->key < b->key) b->l=new;
  else b->r=new;
}

void Preorder(Node t){
  printf(" %d",t->key);
  if(t != NIL){
    if(t->l != NIL)Preorder(t->l);
    if(t->r != NIL)Preorder(t->r);
  }
}
 
void Inorder(Node t){
   
  if(t != NIL){
    if(t->l != NIL){
      Inorder(t->l);
      }
    printf(" %d",t->key);
     
    if(t->r != NIL){
      Inorder(t->r);
      }
  }
}