#include <stdio.h>
#include <stdlib.h>
#define NIL -1
typedef struct {
        int key,right,left;

} N;
void Insert(N *, int, int);
void Preorder(N *, int );
void Inorder(N *, int );
int main (){
        int i,n=0,key,j=0;
        char com[8];
        N *Tree;
        scanf("%d",&n);
        Tree = malloc(sizeof(N)*n);

        for(i=0; i<n; i++) {
                scanf("%s",com);
                if(com[0]=='i') {
                        scanf("%d",&key);
                        Insert(Tree,j,key);
                        j++;
                }
                else if(com[0]=='p') {
                        if(j>0) {
                                Inorder(Tree,0);
                                printf("\n");

                                Preorder(Tree,0);
                                printf("\n");

                        }
                }
        }
        free(Tree);
        return 0;
}
void Insert(N *Tree,int j,int key ){
        int x=0,y;
        Tree[j].key=key;
        Tree[j].left=NIL;
        Tree[j].right=NIL;
        if(j==0) {
                return;
        }
        while( x!= NIL) {
                y=x;
                if(key<Tree[x].key) {
                        x=Tree[x].left;

                }
                else{
                        x=Tree[x].right;
                }
        }
        if(key<Tree[y].key) {
                Tree[y].left=j;
        }
        else{
                Tree[y].right=j;
        }
}
void Preorder(N *Tree, int k){
        if(k==NIL) {
                return;
        }
        printf(" %d",Tree[k].key);
        Preorder(Tree,Tree[k].left);
        Preorder(Tree,Tree[k].right);

}
void Inorder(N *Tree, int k){
        if(k==NIL) {
                return;
        }
        Inorder(Tree,Tree[k].left);
        printf(" %d",Tree[k].key);

        Inorder(Tree,Tree[k].right);

}

