#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define N 200001

typedef struct node *link;
struct node{
  int key;
  link le,ri,pa;
};
link head;
void insert(int a);
void inorder(link h);
void preorder(link h);

int main(){
  char z[10];
  int m,k,i;

  head=NULL;
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%s",z);
    if(strcmp(z,"insert")==0){
      scanf("%d",&k);
      insert(k);
    }
    else if(strcmp(z,"print")==0){
      inorder(head);
      printf("\n");
      preorder(head);
      printf("\n");
    }
  }

  return 0;
}

void insert(int a){
  link x,y,z;
  z=malloc(sizeof(struct node));
  z->key=a; z->le=NULL; z->ri=NULL;
  y=NULL;  x=head;
  while(x!=NULL){
    y=x;
    if(z->key<x->key){ x=x->le;}
    else{ x=x->ri;}
  }
  z->pa=y;

  if(y==NULL){head=z;}
  else if(z->key<y->key){y->le=z;}
  else{y->ri=z;}
}


void inorder(link h){
  if(h==NULL) return;
  inorder(h->le);
  printf(" %d",h->key);
  inorder(h->ri);
}

void preorder(link h){
  if(h==NULL) return;
  printf(" %d",h->key);
  preorder(h->le);
  preorder(h->ri);
}

