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

struct node{
  int me;
  struct node *parent;
  struct node *left;
  struct node *right;
};
typedef struct node *point;
point root;
  
void insert(int );
void list(point);
void list1(point);

int main(){
  int n,i,num1;
  char com[8];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",com);
    if((strcmp(com,"insert"))==0){
      scanf("%d",&num1);
      insert(num1);
    }
    else{
      list(root);
      printf("\n");
      list1(root);
      printf("\n");
    }
  }
  return 0;
}
void insert(int id){
  point x,y,z;
  z=malloc(sizeof(struct node));
  z->me=id;
  z->right=NULL;
  z->left=NULL;
  y=NULL;
  x=root;
  while(x!=NULL){
    y=x;
    if(z->me < x->me)
      x = x->left;
    else
      x = x->right;
  }
  z->parent = y;
  if(y==NULL)
    root = z;
  else if(z->me < y->me)
    y->left = z;
  else
    y->right = z;
}
void list(point x){
  if(x!=NULL){
    list(x->left);
    printf(" %d",x->me);
    list(x->right);
  }
}
void list1(point x){
  if(x!=NULL){
    printf(" %d",x->me);
    list1(x->left);
    list1(x->right);
  }
}

