#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 20

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

typedef struct Node Node;

Node *sum,*num;

void jastin(int hum)
{
  Node *a = sum;
  Node *b = num;
  Node *c;

  c=(Node *)malloc(sizeof(Node));
  c->key = hum;
  c->right = num;
  c->left = num;

  while(a!=num)
    {
      b=a;
      if(c->key<a->key) a=a->left;
	else a=a->right;
    }
  c->parent=b;
  if(b==num)sum=c;
  else{
    if(c->key<b->key)b->left=c;
    else b->right=c;
  }
}
void zin(Node *rum)
{
  if(rum==num)return;
  zin(rum->left);
  printf(" %d",rum->key);
  zin(rum->right);
}
void xu(Node *yum)
{
  if(yum==num)return;
  printf(" %d",yum->key);
  xu(yum->left);
  xu(yum->right);
}
int main(void)
{
  int i,j,k;
  char tum[N];
  
  scanf("%d",&i);
  
  for(j=0;j<i;j++)
    {
      scanf("%s",tum);
      if(!strcmp(tum,"insert")) {
	  scanf("%d",&k);
	  jastin(k);
	}else if(!strcmp(tum,"print")) {
	  zin(sum);
	  printf("\n");
	  xu(sum);
	  printf("\n");
	  }
    }
	return 0;
}
      
  
  

