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


typedef struct node {
    int key;
    struct node *left;
    struct node *right;
} Tree;

Tree *root = NULL;

Tree *make1node(int key) {
    Tree *tree = malloc(sizeof(struct node));
    tree->key = key;
    tree->left = NULL;
    tree->right = NULL;
    return tree;
}

void insert(Tree *tree) {
    Tree *x, *y;
    y = NULL;
    x = root;
    while (x != NULL) {
        y = x;
        if (tree->key < x->key) x = x->left;
        else x = x->right;
    }
    if (y == NULL) root = tree;
    else if (tree->key < y->key) y->left = tree;
    else y->right = tree;
}

void printleft(Tree *tree) {
    if (tree->left != NULL) printleft(tree->left);
    printf(" %d", tree->key);
    if (tree->right != NULL) printleft(tree->right);
}

void printmid(Tree *tree) {
    printf(" %d", tree->key);
    if (tree->left != NULL) printmid(tree->left);
    if (tree->right != NULL) printmid(tree->right);
}

void printtree(Tree *tree) {
    printleft(tree);
    printf("\n");
    printmid(tree);
    printf("\n");
}

int main(void){
    int n, key, i;
    char command[7];
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%s", command);
        if (!strcmp(command, "insert")) {
            scanf("%d", &key);
            insert(make1node(key));
        } else {
            printtree(root);
        }
    }
}
