#include <stdio.h>

typedef struct node {
  int key;
  struct node *p;
  struct node *left;
  struct node *right;
} Node;

void insert(Node*, Node*);
void print_M(Node*);
void print_P(Node*);


Node T[500000];

int main()
{
  int m,k,i;
  char enter[6];
  Node z;

  T[0].key = -1;
  T[0].left = NULL;
  T[0].right = NULL;
  T[0].p = NULL;

  scanf("%d",&m);
  for(i = 0;i < m;i++){
    scanf("%s %d",enter,&k);
    if(strcmp(enter,"insert") == 0){
      z.key = k;
      z.left = NULL;
      z.right = NULL;
      z.p = NULL;
      insert(T[0],&z);
    }
    else {
      print_M(T[0]);
      print_P(T[0]);
    }

    return 0;
}

void insert(Node T, Node *z)
{
  Node x,y;

  y = NULL; //xの親
  x = T[0]; //Tの根
  while(x != NULL){
    y = x; //親を設定
    if(z.key < x.key) x = x.left; //左の子へ移動
    else x = x.right; //右の子へ移動
  }

  z.p = y;

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

void print_M(Node now)
{
  if(now.left->key != -1) print_M(now.left->key);
  print_M(now.p->key);
  if(now.right-> != -1) print_P(now.right->key);
}
   
void print_P(Node now)
{
  print_M(now.p->key);
  if(now.left->key != -1) print_M(now.left->key);
  if(now.right->key != NULL) print_P(now.right->key);
}