#include <stdio.h>

void insert(int);
#define NIL NULL
 struct node{
   struct node *p;
  struct  node *l;
   struct node *r;
   int k;
};
typedef struct node * Node;
void inParse(Node);
void  preParse(Node);
Node Root;
int main(){
Root->k=-1;
Root->l=NIL;
Root->r=NIL;
Root->p=NIL;
int num,c,i;
char w[10];
scanf("%d",&c);
for(i=0;i<c-1;i++){
scanf("%s%d",&w,&num);
insert(num);
}
preParse(Root);
inParse(Root);
return 0;
}

void  preParse(Node u){
	Node x;
	x=u;
    if(x == NIL) return ;
    printf(" %d",*(&x->k));
    preParse(&x->l);
    preParse(&x->r);
}

void inParse(Node u){
	 Node x;
		x=u;
    if (x == NIL) return ;
    inParse(&x->l);
    printf(" %d",*(&x->k));
    inParse(&x->r);
}

void insert(int k){
	Node x;
    x=Root;
while(x != NIL){
 if(k > x->k) x=x->r;
 else x=x->l;
}
x->k=k;
x->l=NIL;
x->r=NIL;
}