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


 
typedef struct NODE {
  
    struct Node {
    int A;
    struct NODE *right;
    struct NODE *left;
    } *node;
  
} *NODE;




typedef struct Node * Node;
 
void PrintPreorder(NODE tree);

void PrintInorder(NODE tree);

void Free(NODE tree);

bool Search(NODE tree, int key);

void Insert(NODE tree, int item);

bool IsEmpty(NODE tree);

void CreateLeaf(NODE leaf, int item);

NODE NewTree(void);
 


int main(void)
{
    int i, n, key;
    
    char com[10], input[100];
    
    NODE bst = NewTree();
 
    scanf("%d\n", &n);
    for (i=0; i<n; i++)
    {
    fgets(input, 100, stdin);
    sscanf(input, "%s %d\n", com, &key);
    if (strcmp(com, "insert") == 0)
        Insert(bst, key);
    else
    {
        PrintInorder(bst);
        puts("");
        PrintPreorder(bst);
        puts("");
    }
    }
 
    Free(bst);
 
    return 0;
}




void PrintPreorder(NODE tree)
{
    if (IsEmpty(tree))
    return;
 
    printf(" %d", tree->node->A);
 
    if (!IsEmpty(tree->node->left))
    PrintPreorder(tree->node->left);   
 
    if (!IsEmpty(tree->node->right))
    PrintPreorder(tree->node->right);  
}



void PrintInorder(NODE tree)
{
    if (IsEmpty(tree))
    return;
 
    if (!IsEmpty(tree->node->left))
    PrintInorder(tree->node->left);    
 
    printf(" %d", tree->node->A);
 
    if (!IsEmpty(tree->node->right))
    PrintInorder(tree->node->right);   
}


void Free(NODE tree)
{
    if (IsEmpty(tree))
    free(tree);
    else
    {
    Free(tree->node->left);
    Free(tree->node->right);
    free(tree->node);
    free(tree);
    }
}





bool Search(NODE tree, int key)
{
    while (1)
    {
    if (IsEmpty(tree))
        return false;
    else if (key < tree->node->A)
        tree = tree->node->left;
    else if (key > tree->node->A)
        tree = tree->node->right;
    else
        return true;
    }
}



void Insert(NODE tree, int item)
{
    while (1)
    {
    if (IsEmpty(tree))
    {
        CreateLeaf(tree, item);
        break;
    }
    else if (item < tree->node->A)
        tree = tree->node->left;
    else if (item > tree->node->A)
        tree = tree->node->right;
    }
}


bool IsEmpty(NODE tree)
{
    return tree->node == NULL;
}



void CreateLeaf(NODE leaf, int item)
{
    leaf->node = (Node)malloc(sizeof(struct Node));
    leaf->node->A = item;
    leaf->node->left = NewTree();
    leaf->node->right = NewTree();
}





NODE NewTree(void)
{
    NODE empty = (NODE)malloc(sizeof(struct NODE));
    empty->node = NULL;
    return empty;
}
 

