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

struct T{
  int key;
  struct T *right;
  struct T *left;
  struct T *parent;
};
typedef struct T *Tree;

void insert(int);
void Mprint(Tree);
void Fprint(Tree);

Tree root;

int main(){
  int x,m,i;
  char s[10];
  
  scanf("%d",&m);

  for(i=0 ; i<m ; i++){
    scanf("%s",s);
    if(0==strcmp(s,"insert")){
      scanf("%d",&x);
      insert(x);
    }

      if(0==strcmp(s,"print")){
      Mprint(root);
      printf("\n");
      Fprint(root);
      printf("\n");
    }
  }

  return 0;
}

void insert(int k){
  Tree y = NULL;
  Tree x = root;
  Tree z;

  z=malloc(sizeof(struct T));
  z->key = k;
  z->right = NULL;
  z->left = NULL;

  while(x!=NULL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right; 
  }

  z->parent=y;

  if(y==NULL)root=z;
  else if(z->key < y->key) y->left=z;
  else y->right=z;
}

void Mprint(Tree A){
  if(A!=NULL){
    Mprint(A->left);
    printf(" %d",A->key);
    Mprint(A->right);
  }
}

void Fprint(Tree A){
 if(A!=NULL){
   printf(" %d",A->key);
   Fprint(A->left);
   Fprint(A->right);
 }
}