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

#define N 500000

struct Node {
    int key;
    struct Node *p,*l,*r;
};

struct Node *NIL,*root;

void inorder(struct Node *);
void preorder(struct Node *);
void insert(int);


int main()??{
    int n,x,i;
    char com[N][10];
    
    scanf("%d",&n);
    
    for(i=0; i<n; i++) {
        scanf("%s",com[i]);
        
        if(strcmp(com[i],"insert")==0) {
            scanf("%d",&x);
            insert(x);
        }
        if(strcmp(com[i],"print")==0) {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }
    
    return 0;
}


void inorder(struct Node *x) {
    if(x==NIL) return;
    
    inorder(x->l);
    printf(" %d",x->key);
    inorder(x->r);
}


void preorder(struct Node *x) {
    if(x==NIL) return;
    
    printf(" %d",x->key);
    preorder(x->l);
    preorder(x->r);
}


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