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

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

Node root;

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(struct node *t)
{
  if(t==NIL)return;
  inorder(t->left);
  printf("%d ",t->key);
  inorder(t->right);
}

void preorder(struct node *t)
{
  if(t==NIL)return;
  printf("%d ",t->key);
  preorder(t->left);
  preorder(t->right);
}

int main()
{
  int i,count,number;
  char order[10];

  scanf("%d",&count);
  for(i=0;i<count;i++)
    {
      scanf("%s",order);
      if(strcmp(order,"insert")==0)
	{
	  scanf("%d",&number);
	  insert(number);
	}
      else if(strcmp(order,"print")==0)
	{
	  inorder(root);
	  printf("\n");
	  preorder(root);
	  printf("\n");
	}
    }
  return 0;
}