#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void insert(int);
void inorder();
void preorder();

typedef struct node {
        int key;
        struct node *right, *left, *parent;
}node;

node *root, *NIL;

int main(){
        int n, i, x;
        char str[6];

        scanf("%d", &n);

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

void insert(int k) {
        node *y = NIL;
        node *x = root;
        node *z;

        z = (node * )malloc(sizeof(node));
        z->key = k;
        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) {
                root = z;
        }
        else{
                if(z->key < y->key) {
                        y->left = z;
                }

                else{
                        y->right = z;
                }
        }
}
void inorder(node *u){
        if(u==NIL) return;
        inorder(u->left);
        printf(" %d", u->key);
        inorder(u->right);
}

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