/* Binary Search Tree <Insert> */
#include <stdio.h>
#include <stdlib.h>

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

typedef struct node * NodePointer;

void init(void);
NodePointer makenode(int);
void insert(int, NodePointer);
void preorder(NodePointer);
void inorder(NodePointer);

NodePointer head, tail;

int main()
{
    char str[7];
    int i, n, k;

    init();
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%s", str);
        if(str[0] == 'i'){
            scanf("%d", &k);
            insert(k, head);
        } else{
            inorder(head -> right);
            printf("\n");
            preorder(head -> right);
            printf("\n");
        }
    }
    return 0;
}

void init(void)
{
    head = makenode(-1);
    tail = makenode(-1);
    head -> right = tail;
    head -> left = tail;
}

NodePointer makenode(int k)
{
    NodePointer x;

    x = malloc(sizeof(struct node));
    x -> key = k;
    x -> left = x -> right = tail;

    return x;
}

void insert(int k, NodePointer p)
{
    if(k < p -> key){
        if(p -> left == tail){
            p -> left = makenode(k);
        } else{
            insert(k, p -> left);
        }
    } else{
        if(p -> right == tail){
            p -> right = makenode(k);
        } else{
            insert(k, p -> right);
        }
    }
}

void preorder(NodePointer node)
{
    if(node != tail){
        printf(" %d", node -> key);
        preorder(node -> left);
        preorder(node -> right);
    }
}

void inorder(NodePointer node)
{
    if(node != tail){
        inorder(node -> left);
        printf(" %d", node -> key);
        inorder(node -> right);
    }
}
