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



struct node{
    int me;
    struct node *parent;
    struct node *left;
    struct node *right;
    
};
 struct node *Tree,*END;
int number;



void input(void){
    char str[100];
    int n;
    int i;
    scanf("%d",&number);
    for(i=0;i<number;i++){
        scanf("%s",str);
        if(strcmp(str,"insert")){
            scanf("%d",&n);
        insert(n);
        }
        else if(strcmp(str,"print")==1){
            Inorder(Tree);
            printf("\n");
            Preorder(Tree);
            printf("\n");
        }
    }
    
    
}

void insert(int n){
    struct node *a=Tree;
    struct node *b=END;
    struct node *c;
    
    c->me=n;
    c->left=END;
    c->right=END;
    
    
    while(b!=END){
        b=a;
        if(c->me < a->me){
            a=a->left;
                    }else {
                        a=a->right;
                    }
                    
                    
    }
    
    c->parent=b;
    if(b==END){
        Tree=c;
        
    }else{
        if(c->me < b-> me){
            b->left=c;
            
            
        }else{
            b->right=c;
        }
        
    }
    
    
    
}

void Inorder(struct node *a){
    if(a==END)return;
    Inorder(a->left);
    printf("%d",a->me);
    Inorder(a->right);
    
    
}

void Preorder(struct node *a){
    if(a==END)return;
    printf("%d",a->me);
    Preorder(a->left);
    Preorder(a->right);
    
}


int main(void) {
    
    input();    
	return 0;
	
}


