#include<stdio.h>
#include<stdlib.h>
 struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};
typedef struct node * Node;
 
Node root;

void ins(int k){
  Node y = NULL;
  Node x = root;
  Node z;
  
  z = malloc(sizeof(struct node));
  z -> key = k;
  z -> l = NULL;
  z -> r = NULL;
 while(x != NULL){
    y = x;
    if(z -> key < x -> key)x = x-> l;
    else x = x->r;
  }
  z -> p = y;
 if(y == NULL)root = z;
  else if(z -> key < y -> key)y -> l = z;
  else y -> r = z;
 
 
}
 
void ino(Node u){
 
  if (u != NULL){
 
    ino(u -> l);
    printf(" %d",u-> key);
    ino(u -> r);
  }
}
void pre(Node u){
 
  if (u != NULL){
 
    printf(" %d",u -> key);
    pre(u -> l);
    pre(u -> r);
  }
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'i' ){
      scanf("%d", &x);
      ins(x);
    } else if ( com[0] == 'p' ){
    ino(root);
    printf("\n");
    pre(root);
    printf("\n");
    } 
}
return 0;
}