#include<stdio.h>
#include<stdlib.h>
#define N 10000
#define NIL NULL
struct node{
  int key;
  struct node *left;
  struct node *right;
  struct node *parent;
};
 
typedef struct node * Node;
Node root;
 
void insert(int k){
  Node x = root;
  Node y = NIL;
  Node z;

  
  z = malloc(sizeof(struct node));
  z->key = k;
  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(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" ");
    printf("%d",u->key);
    inorder(u->right);
  }
  
}
void preorder(Node u){ 
    if (u != NIL) {
      printf(" ");
      printf("%d",u->key); 
      preorder(u->left);
      preorder(u->right);
     
    }
}
 
int main(){
  
  int n,m,i,j;
  char str[10];
  
  scanf("%d",&m);
  
  for(i=0;i<m;i++){
    scanf("%s",str);
    
    if(str[0]=='i'){  
      scanf("%d",&n);
      insert(n);}
    
    else{
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  
  return 0;
}