// Slower C++ solution:
#include <stdio.h>

#include <iostream>

using namespace std;



struct Node{

    int key;

    Node *parent;

    Node *left;

    Node *right;

};



struct Node *NIL, *root;



void init(){

    root = NIL;

}



void insert(Node* z){

    struct Node* y = NIL; // xの親

    struct Node* x = root;



    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 print_node_inorder(Node* x){

    if(x == NIL){

        return;

    }

    print_node_inorder(x->left);

    printf(" %d", x->key);

    print_node_inorder(x->right);

}



void print_node_pre(Node* x){

    if(x == NIL){

        return;

    }

    printf(" %d", x->key);

    print_node_pre(x->left);

    print_node_pre(x->right);

}



void print_(){

    print_node_inorder(root);

    printf("\n");

    print_node_pre(root);

    printf("\n");

}



int main(void){

    void init();

    

    int m;

    scanf("%d", &m);



    string com;



    for(int i = 0; i < m; i++){

        cin >> com;

        if(com == "insert"){

            struct Node* n;

            n = (struct Node*)malloc(sizeof(struct Node));

            n->right = NIL;

            n->left = NIL;

            n->parent = NIL;

            scanf("%d", &n->key);

            insert(n);

        }else if(com == "print"){

            print_();

        }else{

            printf("invalid command");

        }

    }



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.15933980157289x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define NIL -1



struct Node{

    int num;

    struct Node* left;

    struct Node* right;

};



struct Node* root;



void insert(int num, struct Node* n){

    if(root == NULL){

        root = (Node*) malloc(sizeof(struct Node));

        root->num = num;

        root->left = NULL;

        root->right = NULL;

        return;

    }



    if(num < n->num){

        if(n->left == NULL){

            n->left = (Node*) malloc(sizeof(struct Node));

            n->left->num = num;

            n->left->left = NULL;

            n->left->right = NULL;

        }else{

            insert(num, n->left);

        }

    }else{

        if(n->right == NULL){

            n->right = (Node*) malloc(sizeof(struct Node));

            n->right->num = num;

            n->right->left = NULL;

            n->right->right = NULL;

        }else{

            insert(num, n->right);

        }

    }

}



void print_middle(struct Node* n){

    if(n == NULL){

        return;

    }

    print_middle(n->left);

    printf(" %d", n->num);

    print_middle(n->right);

}



void print_before(struct Node* n){

    if(n == NULL){

        return;

    }

    printf(" %d", n->num);

    print_before(n->left);

    print_before(n->right);

}



void init(){

    root = NULL;

}



int main(void){

    init();



    int N;

    scanf("%d", &N);



    for(int i = 0; i < N; i++){

        char comm[100];

        int num;

        scanf("%s", comm);



        if(comm[0] == 'i'){

            scanf("%d", &num);

            insert(num, root);

        }else if(comm[0] == 'p'){

            print_middle(root);

            printf("\n");

            print_before(root);

            printf("\n");

        }

    }

}