#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 500000

struct node
{
    int key;
    struct node* p;
    struct node *l, *r;
} typedef node;

void Insert(node*);
int Inorder(int, node*);
int Preorder(int, node*);

node *root = NULL;

int main()
{
    int i;
    int n;
    int key;
    char order[7];
    node *new;

    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        scanf("%s", order);
 
        if(strcmp(order, "insert") == 0)
        {
            new = (node*)malloc(sizeof(node));
	        scanf("%d", &(new->key));
	        new->l = NULL;
	        new->r = NULL;
	        Insert(new);
	    }
        if(strcmp(order, "print") == 0)
        {
            Inorder(n, root);
            Preorder(n, root);
        }
    }
    return 0;
}

void Insert(node *z)
{
    node *x, *y;

    y = NULL;
    x = root;

    while(x != NULL)
    {
        y = x;
        if(z->key < x->key) x = x->l;
        else x = x->r;
    }
    z->p = y;

    if(y == NULL) root = z;
    else if(z->key < y->key) y->l = z;
    else y->r = z;
}  

int Inorder(int n, node *x)
{
    if(x == NULL) return n;

    n = Inorder(n, x->l);
    if(n != 2)
    {
        printf("%d ", x->key);
        n--;
    }
    else printf("%d\n", x->key);
    n = Inorder(n, x->r);
    
    return n;
}

int Preorder(int n, node *x)
{
    if(x == NULL) return n;
    
    if(n != 2)
    {
        printf("%d ", x->key);
        n--;
    }
    else printf("%d\n", x->key);
    n = Preorder(n, x->l);
    n = Preorder(n, x->r);
    
    return n;
}