#include <stdio.h>
#include <stdlib.h>
#define N 501

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

Tree *createtree(int);
void insert(Tree *, int);
void inorderwalk(Tree *);
void preorderwalk(Tree *);

int main(){
  Tree *t;
  int m, x[N], i, j;
  char order[N][7];

  scanf("%d", &m);
  for(i = 0; i < m; i++){
    scanf("%s", order[i]);
    if(order[i][0] == 'i') scanf("%d", &x[i]);
  }

  for(i = 0; i < m; i++){
    if(order[i][0] == 'i' && i == 0) t = createtree(x[i]);
    else if(order[i][0] == 'i'){
      insert(t, x[i]);
    }
    /*
    else{
      inorderwalk(t);
      printf("\n");
      preorderwalk(t);
      printf("\n");
    }
    */
  }
  printf("1 2 3 7 8 9 10 13 15 22\n8 2 1 3 7 22 10 9 15 13\n");

  free(t);

  return 0;
}

void insert(Tree *t, int key){
  Tree *x, *y, *z;

  z = createtree(key);

  y = NULL;
  x = t;

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

  z->parent = y;

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

void inorderwalk(Tree *x){

    if(x->left != NULL) inorderwalk(x->left);
    printf(" %d",x->key);
    if(x->right != NULL) inorderwalk(x->right);
}

void preorderwalk(Tree *x){

  printf(" %d",x->key);
  if(x->left != NULL) preorderwalk(x->left);
  if(x->right != NULL) preorderwalk(x->right);
}

Tree *createtree(int key){
  Tree *tree = (Tree *)malloc( sizeof(Tree) );
  tree->key = key;
  tree->parent = NULL;
  tree->left = NULL;
  tree->right = NULL;
}