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

struct Node {
  int key;
  struct Node *parent,*left,*right;
};

  struct Node *root,*Nil;

void insert(int a){
  struct Node *x=root,*y=Nil,*z;

  z=(struct Node *)malloc(sizeof(struct Node));
  z->key=a;
  z->left=Nil;
  z->right=Nil;

  while(x!=Nil){
    y=x;
    if(z->key < x->key){x=x->left;}
    else {x=x->right;}
  }
 z->parent=y;

 if(y==Nil){root=z;}
 else {
   if(z->key < y->key){y->left=z;}
   else {y->right=z;}
 }
}

void inorder(struct Node *x){
  if(x==Nil)return;
  inorder(x->left);
  printf(" %d",x->key);
  inorder(x->right);
}

void preorder(struct Node *x){
  if(x==Nil)return;
  printf(" %d",x->key);
  preorder(x->left);
  preorder(x->right);
}
int main(){
  int n,i,q;
  char co[10];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",co[i]);
    if(co=="insert"){
      scanf("%d",&q);
      insert(q);
    }
    else if(co=="print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



