/*#include<stdio.h>
#include<string.h>

#define MAX_NUMBER_OF_ORDER 500000
#define INDEX_OF_ROOT 0


struct Node
{
  int id;
  struct Node *parent;
  struct Node *left;
  struct Node *right;
};

void insert(struct Node);
void print_inorder();
  
struct Node node[MAX_NUMBER_OF_ORDER];
//int number_of_node = 0;

int main()
{
  int number_of_order,i,j,id,number_of_node = 0;
  int order;
  scanf("%d",&number_of_order);
  for(i = 0 ; i < number_of_order -1 ; i++)
    {
      node[i].parent = NULL;
      node[i].left = NULL;
      node[i].right = NULL;
    }

  for(i = 0 ; i < number_of_order ; i++)
    {
      scanf("%d",&order);
      if(order == 1)
	{
	  
	  scanf("%d",&node[number_of_node].id);
	    insert(node[number_of_node]);
	  number_of_node++;
	}
      else if(order ==0)print_inorder();
      // printf("test1");
      for(j = 0;j <= i ; j++)
	{
	  printf("node[%d] = %d\n",j,node[j].id);
	  //if(node[j].left!= NULL)printf("node[%d]->left->id = %d\n",j,(node[j].left)->id);
	  //if(node[j].right != NULL)printf("node[%d]->right->id = %d\n",j,(node[j].right)->id);
	}
	
	
      
    }

}

void insert(struct Node z)
{
  struct Node *x = &node[INDEX_OF_ROOT];
  struct Node *y = NULL;

  while(x != NULL)
    {
      y = x;
      if(z.id < x->id)
	{
	  
	  x = x->left;
	  
	}
      else
	{
	  
	  x = x->right;
      
	}
    }

  //&z = y;
  
  if(y == NULL)node[INDEX_OF_ROOT] = z ;
  else if( z.id < y->id ) y->left = &z;
  else y->right = &z;

}

/*
void print_inorder()
{
  int i = INDEX_OF_ROOT;
  while(node[i] != NULL)
    {
      printf("test1\n");
      if(x->left != NULL)
	{
	  x = x->left;
	  printf("test2\n");
	  continue;
	}
      else
	{
	  while(x->right == NULL)
	    {

	      printf("%d ",x->id);
	      x = x->parent;
	      printf("test3\n");
	    }
	  
	  if(x -> right !=NULL)
	    {
	      printf("%d ",x->id);
	      x = x->right;
	      printf("test4\n");
	    }

	  
	   
	}
      printf("test5\n");
      break;
    }


 
}



void print_inorder()
{
  struct Node *x= &node[INDEX_OF_ROOT];
  printf("Root = %d\n",x->id);
  x=&(x->left);
  //printf("left = %d\n",x->left->id);
   printf("left = %d\n",x->id);
  while(x != NULL)
    {
      printf("test1\n");
      if(x->left != NULL)
	{
	  x = x->left;
	  printf("test2\n");
	  continue;
	}
      else
	{
	  while(x->right == NULL)
	    {

	      printf("%d ",x->id);
	      x = x->parent;
	      printf("test3\n");
	    }
	  
	  if(x -> right !=NULL)
	    {
	      printf("%d ",x->id);
	      x = x->right;
	      printf("test4\n");
	    }

	  
	   
	}
      printf("test5\n");
      break;
    }


 
}

*/

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


#define INDEX_OF_ROOT 0


struct Node
{
  int id;
  struct Node *parent;
  struct Node *left;
  struct Node *right;
};

void insert(int);
void print_inorder(struct Node *);
void print_preorder(struct Node *);
  
struct Node *node[2];
//int number_of_node = 0;

int main()
{
  int number_of_order,i,j,id,number_of_node = 0;
  //int order;
  char order[7];
  scanf("%d",&number_of_order);
  

  for(i = 0 ; i < number_of_order ; i++)
    {
      scanf("%s",&order);
      if(strcmp(order,"insert") == 0)
	{
	  
	  scanf("%d",&id);
	    insert(id);
	  
	}
      else if(strcmp(order,"print")==0)
	{
	  print_inorder(node[INDEX_OF_ROOT]);
	  printf("\n");
	  print_preorder(node[INDEX_OF_ROOT]);
	  printf("\n");
	}
      // printf("test1");
      /*
      for(j = 0;j <= i ; j++)
	{
	  printf("node[%d] = %d\n",j,node[j].id);
	  if(node[j].left!= NULL)printf("node[%d]->left->id = %d\n",j,(node[j].left)->id);
	  if(node[j].right != NULL)printf("node[%d]->right->id = %d\n",j,(node[j].right)->id);
	}
      */
	
      
    }

}

void insert(int id)
{
  struct Node *x = node[INDEX_OF_ROOT];
  struct Node *y = node[1];
  struct Node *z;

  z = malloc(sizeof(struct Node));
  
  z -> id = id;
  z ->left = NULL;
  z ->right = NULL;
  
  while(x != NULL)
    {
      y = x;
      if(z ->id < x->id) 
	{
	  x = x->left;
	}
      else
	{
	  x = x->right;
	}
    }

  z -> parent = y;

  
  if(y == NULL)node[INDEX_OF_ROOT] = z;
  else if( z->id < y->id ) y->left = z;
  else y->right = z;


}





void print_inorder(struct Node *target)
{
  //struct Node *target;
  if(target == NULL) return;
  if(target->left != NULL)print_inorder(target->left);
  printf(" %d",target->id);
  if(target ->right!=NULL)print_inorder(target->right);
}


void print_preorder(struct Node *target)
{

  if(target == NULL)return;
  printf(" %d",target -> id);
  print_preorder(target->left);
  print_preorder(target ->right);

}

