#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NIL NULL

int key;
struct node{
  int key;
  struct node *left;
  struct node *right;
  struct node *parent;
};
  typedef struct node * Node;

Node Tree;

 void insert(int k){
   Node y = NIL;
   Node x = Tree;
   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){
       Tree = z;
     }
     else if( z->key < y->key ){
       y->left = z;
     }
     else{
       y->right = z;
     }
 }

     void InOrder(Node T){
       if(T == NIL) return;
	 InOrder(T->left);
	 printf(" %d", T->key);
	 InOrder(T->right);
       }
     

       void PreOrder(Node T){
	     if(T == NIL) return;
	   printf(" %d", T->key);
	   PreOrder(T->left);
	   PreOrder(T->right);
	 }
       
      
int main(){
  int i,x,n;
  char c[5];

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%s", c);
    if(strcmp(c,"insert")==0){
      scanf("%d", &x);
      insert(x);
    }

    else if(strcmp(c,"print")==0){
      if(Tree != NIL){
	InOrder(Tree);
      }
	printf("\n");
	if(Tree != NIL){
	PreOrder(Tree);
	}
	printf("\n");
    }
  }

  return 0;
}