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

#define MAX 100000
#define NIL -1

typedef struct search{
  struct search *right;
  struct search *left;
  struct search *p;
  int key;

}search;

void insert(int);
void  inorderTreeWalk(search *x);
void Puriorder(search *x); 
search *T;

int main(){
  int i,v,k;
  char a[32];

  T = NULL;

  scanf("%d",&v);
  for ( i = 0;i < v;i++){
    scanf("%s",a);
    if(strcmp(a,"insert")==0){
      scanf("%d",&k);
    insert(k);
    }
    else if(strcmp(a,"print")==0){
      inorderTreeWalk(T);
      printf("\n");
      Puriorder(T);
      printf("\n");
      }

  }
  return 0;
}


  //出力
void  inorderTreeWalk(search *x){
    if(x !=NULL){
      inorderTreeWalk(x->left);
    printf(" %d",x->key);
    inorderTreeWalk(x->right);
    }
}

void Puriorder(search *x){
 if(x !=NULL){ 
   printf(" %d",x->key);
      Puriorder(x->left);
      Puriorder(x->right);
    }
}







void insert(int key){
  search *x,*y,*z;
  y = NULL; // x の親
  x = T;
  z = (search *)malloc(sizeof(search));
  z->key = key;
  z->right = NULL;
  z->left = NULL;
  z->p = NULL;
  while (x != NULL){
    y = x; // 親を設定
    if (z->key < x->key)
      x = x->left; // 左の子へ移動
    else 
      x = x->right; // 右の子へ移動
  }
  z->p = y;

  if( y == NULL){ // T が空の場合
    T = z;
  }
  else if (z->key < y->key)
    y->left = z; // z を y の左の子にする
  else 
    y->right = z; // z を y の右の子にする
}