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


int s=0,h=0;

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

typedef struct node * Node;


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






#define NIL NULL

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(Node u)
{
  if(u==NIL)return;
  inorder(u->left);

  printf(" %d",u->key);
  inorder(u->right);
  s++;
}

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



int main()
{
  int n,i,x;
  char com[10];

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

  return 0;
  
}

