#include <stdio.h>
#define MAX 500001
#define NIL -1

struct Node{
  int p;
  int l;
  int r;
};

struct Node T[MAX];

void insert(int index, int key){

  int x = 0;
  int y = NIL;

  T[index].p = key;
  T[index].l = NIL;
    T[index].r = NIL;

  if( index == NIL ){
    return;
  }

  while( x != NIL ){

    y = x;

    if( key < T[x].p ){
      x = T[x].l;
    }else{
      x = T[x].r;
    }

  }

  if( key < T[y].p ){
    T[y].l = key;
  }else{
    T[y].r = key;
  }



}

void print_inorder(int u){

  if( u == NIL ){
    return;
  }

  print_inorder(T[u].l);
  printf(" %d",T[u].p);
  print_inorder(T[u].r);

}

void print_preorder(int u){

  if( u == NIL ){
    return;
  }

  printf(" %d",T[u].p);
  print_preorder(T[u].l);
  print_preorder(T[u].r);

}


int main(int argc, char const *argv[]) {

  int n,i,key;
  char order[8];
  int index = 0;

  scanf("%d",&n);

  for( i = 0 ; i < n ; i++ ){

    scanf("%s",order);

    if( order[0] == 'i' ){

      scanf("%d",&key);
      insert(index,key);
      index++;

    }else{

      if( index > 0 ){

        print_inorder(0);
        printf("\n");
        print_preorder(0);
        printf("\n");

      }

    }


  }






  return 0;
}