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

#define MAX 500000

void ins(int);
void Pre(int);
void Ino(int);


typedef struct{
  int key;
  int p;
  int l[2];
} Node;

Node t[MAX];

int main(){
  int i, n;
  char s[7];

      scanf("%d", &n);

      for(i = 0; i < n; i++){
        t[i].key = -1;
        t[i].l[0] = -1;
        t[i].l[1] = -1;
      }


      for(i = 0; i < n; i++){
        scanf("%s", s);
        if(strcmp(s, "insert") == 0){
          scanf("%d", &t[i].key);
          ins(i);
        }
        else if(strcmp(s, "print") == 0){
          Ino(0);
          printf("\n");
          Pre(0);
          printf("\n");
        }
      }

      return 0;
}

void ins(z){
  int x, y;

    y = -1;
  x = 0;

      while(1){
    if(x == -1 || z == 0) break;
    y = x;
    if(t[z].key < t[x].key) x = t[x].l[0];
    else x = t[x].l[1];
    }

          t[z].p = y;
              if(y != -1){
    if(t[z].key < t[y].key) t[y].l[0] = z;
    else t[y].l[1] = z;
    }
}


void Pre(int a){
  printf(" %d", t[a].key);

    if(t[a].l[0] != -1) Pre(t[a].l[0]);
  if(t[a].l[1] != -1) Pre(t[a].l[1]);
}


void Ino(int a){
  if(t[a].l[0] == -1){
    printf(" %d", t[a].key);
    if(t[a].l[1] != -1) Ino(t[a].l[1]);
    }
  else{
    Ino(t[a].l[0]);
    printf(" %d", t[a].key);
    if(t[a].l[1] != -1) Ino(t[a].l[1]);
    }
}