#include<stdio.h>
#include<stdlib.h>

struct Node{
  int key;
  struct Node *a;
  struct Node *b;
  struct Node *c;
};
typedef struct Node * Nodepointer;

Nodepointer root,nil;

void insert(int i){
  Nodepointer x = root;
  Nodepointer y = nil; /*parent*/
  Nodepointer z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = i;
  z->b = nil;
  z->c = nil;

  while(x != nil){
    y = x;
    if(x->key > z->key) x = x->b;
    else x = x->c;
  }

  z->a = y;

  if(y == nil) root = z;
  else{
    if(y->key > z->key) y->b = z;
    else y->c = z;
  }

}

void pre(Nodepointer x){
    if(x == nil) return;
    printf(" %d",x->key);
    pre(x->b);
    pre(x->c);
}


void in(Nodepointer x){
    if(x == nil) return;
    in(x->b);
    printf(" %d",x->key);
    in(x->c);
}



int main(){
  int n,i,num;
  char ch[20];

  scanf("%d",&n);

  for(i = 0;i < n;i++){
    scanf("%s",&ch);
    if(ch[0] == 'i'){
      scanf("%d",&num);
      insert(num);
    }
    else if(ch[0] == 'p'){
      in(root);
      printf("\n");
      pre(root);
      printf("\n");
    }
  }
  return 0;
}

