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

struct node{
  int key;
  struct node *r;
  struct node *l;
  struct node *p;
    };
typedef struct node  Node;
void insert(int);
void inorder(Node *);
void preorder(Node *);


Node *root,*NIL;
int main()
{
  int n,i,x;
  char A[20],b[20]="insert",c[20]="print";
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%s",A);
      if(strcmp(A,b)==0){
	scanf("%d",&x);
	insert(x);
      }
      else if(strcmp(A,c)==0){
	inorder(root);
	printf("\n");
	preorder(root);
	printf("\n");
      }
    }

 
  return 0;
}

void insert(int a)
{
  
 Node  *y=NIL;
 Node *x=root;
 Node *z;
 z=(Node *)malloc(sizeof(Node));
 z->key =a;
 z->l=NIL;
 z->r=NIL;
  while(x!=NIL)
    {
      y=x;
      if(z->key < x->key) x=x->l;
      else x=x->r;
    }
  z->p=y;
  if( y==NIL){
    root=z;
  }
  else if(z->key <y->key) y->l=z;
  else y->r=z;
  
}
void inorder(Node *a)
{
  if(a==NIL) return ;
  inorder(a->l);
  printf(" %d",a->key);
  
  inorder(a->r);
}
void preorder(Node *a)
{
  if(a==NIL) return ;
  printf(" %d",a->key);
  preorder(a->l);
  preorder(a->r);
  
}

