#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_ORDER 500000
#define MAX_PRINT 10

struct Node{
    int key;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
};
struct Node *head,*NIL;

int Datanum = 0;
int count = 0;

void Insert(int in){
    struct Node *y = NIL;
    struct Node *x = head;
    struct Node *z = malloc(sizeof(struct Node));
    z->key = in;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL){
        y = x;
        if(z->key < x->key) x=x->left;
        else x = x->right;
    }
    z->parent = y;

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

void PrintPreorder(struct Node *u){
    if(u == NIL) return;
    printf(" %d",u->key);
    PrintPreorder(u->left);
    PrintPreorder(u->right);
}

void PrintInorder(struct Node *u){
    if(u == NIL) return;
    PrintInorder(u->left);
    printf(" %d",u->key);
    PrintInorder(u->right);
}

int main(){
    int n,i,innum;
    char order[7];

    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%s",order);
        if(order[0] == 'i'){
            scanf("%d",&innum);
            Insert(innum);
            Datanum++;
        }else if(order[0] == 'p'){
            PrintInorder(head);
            printf("\n");
            count = 0;
            PrintPreorder(head);
            printf("\n");
            count = 0;
        }else{
            printf("Invalid Order!!\n");
            exit(1);
        }
    }

    return 0;
}
