#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
 
Node root;
 
void insert(int k){
  Node y = NIL; // parent of x
  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)
    {
      inorder(u->left);
      printf("%d ", u->key);
      inorder(u->right);
    }
}
 
void preorder(Node u){
  if(u != NIL)
    {
      printf("%d ", u->key);
      preorder(u->left);
      preorder(u->right);
    }
} 
 
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;
}