#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void insert(int);
struct node{
  int key;
  struct node *p;
  struct node *right;
  struct node *left;
};
struct node *Node,*NIL;


void insert(int a){
   struct node *y=NIL;
   struct node *x=Node;
   struct node *z;
   z = malloc(sizeof(struct node));
    z->key=a;
    z->left=NIL;
    z->right=NIL;
    while(x!=NIL){
        y=x;
        if(z->key<x->key){
            x=x->left;
        }else{
            x=x->right;
        }
    }
    z->p=y;
    if(y == NIL){
        Node=z;
    }else{
        if(z->key < y->key){
            y->left=z;
        }else{
            y->right=z;
        }
    }
}
void pre(struct node *a){
  if(a==NIL)return;
  printf(" %d",a->key);
  pre(a->left);
  pre(a->right);
}
void in(struct node *a){
  if(a==NIL)return;
  in(a->left);
  printf(" %d",a->key);
  in(a->right);
}
int main(){
  int i,j,n;
  char M[10];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",M);
    if(strcmp(M,"insert")==0){
    scanf("%d",&j);
    insert(j);
    }else if(strcmp(M,"print")==0){
      in(Node);
      printf("\n");
      pre(Node);
      printf("\n");
    }
  }
  return 0;
  
}

