
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
struct Node{
    int key;
    struct Node *parent,*left,*right;
};
struct Node *root,*NIL;

void insert(int k){
    struct Node *y=NIL,*x=root,*z;
    z=(struct Node *)malloc(sizeof(struct Node));
    z->key=k;
    z->left=NIL;
    z->right=NIL;
    
    while(x!=NIL){
        y=x;
        if(z->key < y->key)x=x->left;
        else x=x->right;
    }
    z->parent=y;
    if(y==NIL)root=z;
    else if(z->key <y->key)y->left=z;
    else y->right=z;
}

void pre(struct Node *u){
    printf(" %d",u->key);
    pre(u->left);
    pre(u->right);
    printf("\n");
}
void in(struct Node *u){
    pre(u->left);
    printf(" %d",u->key);
    pre(u->right);
    printf("\n");
}

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        char s[7];
        if(strcmp(s,"insert")!=0){
            int a;
            scanf("%d",&a);
            insert(a);
        }else{
            pre(root);
            in(root);
        }
    }
    return 0;
}