#include<stdio.h>
#define NIL -1
#define MAX 500000
int root = NIL;
int key[MAX];
int left[MAX];
int right[MAX];
//int T[MAX];
int p[MAX];
void tree_insert(int z){
  int y = NIL;
  int x = root;
  while(x!=NIL){
    y = x;
    if(key[z] < key[x])x = left[x];
    else x = right[x];
  }
  p[z] = y;
  if(y == NIL)root = z;
  else if(key[z]<key[y])left[y] = z;
  else right[y] = z;
  
}
void preorder(int t){
  if(t==NIL)return;
  printf(" %d",key[t]);
  preorder(left[t]);
  preorder(right[t]);
}

void inorder(int t){
  if(t==NIL)return;
  inorder(left[t]);
  printf(" %d",key[t]);
  inorder(right[t]);
}

void print(){
  inorder(root);
  printf("\n");
  preorder(root);
  printf("\n");
}

int main(){
  
  int i,n,x;
  int z = 0;
  char A[10];
  scanf("%d",&n);
  for(i=0;i<MAX;i++){
    key[i]=NIL;
    left[i]=NIL;
    right[i]=NIL;
    //   T[MAX]=NIL;
    p[i]=NIL;
  }
  for(i=0;i<n;i++){
    scanf("%s", A);
    if(A[0]=='i'){
      scanf("%d",&x);
      key[z]=x;
      tree_insert(z);
      z++;
    }
    else if(A[0]=='p')print();
  }
  
  return 0;
}