#include<stdio.h>
#include<stdlib.h>
#define NIL NULL
struct node{
  int key;
  struct node *right,*left,*parent;
};
typedef struct node*Node;
Node root;

Node treeMin(Node x){
 
  while(x->left!=NIL)
    {
      x=x->left;
    }
  return x;
}
  
Node treeS(Node u, int k){
 
  if(u == NIL || k == u->key)
    {
      return u;
    }
   
  if(k < u->key)
    {
      return treeS(u->left, k);
    }
  else{
    return treeS(u->right,k);
  }
}
 
Node treeSuc(Node x){
 
  Node y;
   
  if(x->right != NIL)
    {
      return treeMin(x->right);
    }
   
  y = x->parent;
 
  while(y != NIL && x == y->right)
    {
      x = y;
      y = y->parent;
    }
  return y;
}
 
void treeD(Node z){
  Node y; 
  Node x; 
}
void insert(int k){
  Node y=NIL;
  Node x=root;
  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)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int main(){
    int n, i, x;
    char com[20];
    scanf("%d", &n);
    for (i=0;i<n;i++)
      {
	if (com[0]=='i')
	  {
	    scanf("%d", &x);
	    insert(x);
	  }
	else if (com[0]=='p')
	  {
	    inorder(root);
	    printf("\n");
	    preorder(root);
	    printf("\n");
	  }
      }
    return 0;
  }
}