#include<stdio.h>
#include<string.h>
#define N 500000
#define M 200000000

typedef struct pointnode{
  int key;
  struct pointnode *p;
  struct pointnode *l;
  struct pointnode *r;
} tree;
tree* treeroot=NULL;

tree* newnode(int);
void treeinsert(tree* ,tree*);
void IOtreeW(tree*);

int main(void){
  int n,i,k;
  char c[10];
  tree* z;
  scanf("%d",&n);
  i=0;
  while(scanf("%s",c)!=EOF || n<N){
    if(strcmp(c,"insert")==0){
      scanf("%d",&k);
      z=newnode(k); 
      treeinsert(treeroot,z);
    }
   else{
      IOtreeW(treeroot);
    }
    i++;
    if(i>=n)break;
  }

  return 0;

}

tree* newnode(int k){
  tree* t;
  t->l=NULL;
  t->r=NULL;
  t->p=NULL;
  t->key=k;

  return t;
}

void treeinsert(tree* t,tree* z){
  tree* y;
  tree* x;
  y=NULL;
  x=treeroot;

  while(x!=NULL){
    y=x;
    if(z->key<x->key){
      x=x->l;
    }
    else{
      x=x->r;
    }
  }
  z->p=y;
  if(y==NULL){
    treeroot=z;
  }
  else if(z->key<y->key){
    y->l=z;
  }
  else{
    y->r=z;
  }
  return ;
}
void IOtreeW(tree* x){
  if(x!=NULL){
    IOtreeW(x->l);
    printf("%d ",x->key);
    IOtreeW(x->r);
  }
  return ;
}