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

typedef struct node *link;

struct node{
    int key;
    link left,right,parent;
};
link head;

void insert(int);
void inorder(link);
void preorder(link);

int main(){
    int m,k;
    char jud[10];
    int i;

    head = NULL;

    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%s",jud);
        if(strcmp(jud,"insert") == 0){
            scanf("%d",&k);
            insert(k);
        }
        else if(strcmp(jud,"print") == 0){
            inorder(head);
            printf("\n");
            preorder(head);
            printf("\n");
        }
    }
    return 0;
}

void insert(int k){
    link x,y,z;
    z = malloc(sizeof(struct node));
    z->key=k;
    z->left=NULL;
    z->right=NULL;
    y=NULL;
    x=head;
    while(x!=NULL){
        y=x;
        if(z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;

    if(y==NULL) head = z;
    else if(z->key < y->key) y->left = z;
    else y->right = z;
}

void inorder(link h){
    if(h==NULL) return;
    inorder(h->left);
    printf(" %d",h->key);
    inorder(h->right);
}

void preorder(link h){
    if(h==NULL) return;
    printf(" %d",h->key);
    preorder(h->left);
    preorder(h->right);
}

