#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NIL -1

typedef struct node{
  int key;
  struct node *left;
  struct node *right;
}Tree;

void insert(Tree *p1, int key){
  Tree *p2;
  int x = p1->key;

  if(p1->key <= key){
    if(p1->right == NULL){
      p2 = malloc(sizeof(Tree));
      p2->key = key;
      p2->left = NULL;
      p2->right = NULL;
      p1->right = p2;
    } else {
      insert(p1->right, key);
    }
  } else {
    if(p1->left == NULL){
      p2 = malloc(sizeof(Tree));
      p2->key = key;
      p2->left = NULL;
      p2->right = NULL;
      p1->left = p2;
    } else {
      insert(p1->left, key);
    }
  }
}

void print_F(Tree *p1){
  if(p1 == NULL) return;
  if(p1->key != NIL) printf("%d ", p1->key);
  print_F(p1->left);
  print_F(p1->right);
}

void print_C(Tree *p1){
  if(p1 == NULL) return;
  print_C(p1->left);
  if(p1->key != NIL) printf("%d ", p1->key);
  print_C(p1->right);
}

int main(){
  Tree *top, *p1;
  int  i, n, key, Flug;
  char c;
  char com[20];

  scanf("%d\n", &n);
  //初期化
  top = malloc(sizeof(Tree));
  top->key = NIL;
  top->left = NULL;
  top->right = NULL;
  p1 = top;

  for (i = 0; i < n; i++) {
    scanf("%s%d", com, &key);
    if(com[0] == 'i'){
      if(Flug == 0){
        p1->key = key;
        Flug = 1;
      } else{
        insert(p1, key);
      }
    }
    else if(com[0] == 'p'){
      print_C(p1);
      printf("\n");
      print_F(p1);
      printf("\n");
    }
  }

  free(top);
  free(p1);
  return 0;
}

