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

int m;

typedef struct{
  int sa,yuu,key,pa;
  int root;
}Ki;

Ki tree[100000];

void tyuukan(int u){
  if(u==-1)return;
  tyuukan(tree[u].sa);
  printf(" %d",tree[u].key);
  tyuukan(tree[u].yuu);
}

void insert(int z){
  int i;
  int y=-1;
  int x=tree[0].root;

  printf("%d\n",tree[z].key);

  while(x!=-1){
    y=x;
    if(tree[z].key<tree[x].key)x=tree[x].sa;
    else x=tree[x].yuu;
  }
  tree[z].pa=y;
  if(y==-1) tree[0].root=z;
  else if(tree[z].key<tree[y].key)tree[y].sa=z;
  else tree[y].yuu=z;
}

int main(){
  int i;
  char C[6];
  int k;
  
  scanf("%d",&m);

   for(i=0;i<m;i++){
    tree[i].root=tree[i].pa=tree[i].key=tree[i].sa=tree[i].yuu=-1;
  }

  for(i=0;i<m;i++){
    scanf(" %s",C);

    if(strcmp(C,"insert")==0){
      scanf(" %d",&k);
      tree[i].key=k;
      insert(i);
    }
    else {
      m-=1;
      break;
    }

  }
  tyuukan(0);
  return 0;
}

