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

#define NIL NULL


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

typedef struct node * Node;

Node root;

void preorder(Node);
void inorder(Node);
void insert(int);

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

  return 0;
}

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 x)
{
  if(x!=NIL)
    {
      inorder(x->left);
      printf(" %d",x->key);
      inorder(x->right);
    }
}

void preorder(Node x)
{
  if(x!=NIL)
    {
      printf(" %d",x->key);
      preorder(x->left);
      preorder(x->right);
    }
}