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

struct node{
    struct node *Left;
    struct node *Right;
    struct node *Parent;
    int ndkey;
};

typedef struct node * NodePointer;

NodePointer root = NULL;
NodePointer NIL = NULL;

NodePointer makeNode(){
    NodePointer node = malloc(sizeof(struct node));
    node->Left = NULL;
    node->Right = NULL;
    node->Parent = NULL;
    node->ndkey = 0;
    return node;
}

void insert(int ndkey){
    NodePointer z = makeNode();
    NodePointer x = root;
    NodePointer y = NIL;
    z -> ndkey = ndkey;

    while(x!=NIL){
        y = x;
        if(z->ndkey < y->ndkey) x = x -> Left;
        else x = x -> Right;
    }

    z -> Parent = y;
    if(y == NIL) root = z;
    else if(z -> ndkey < y -> ndkey) y -> Left = z;
    else y -> Right = z;
}

void preO(NodePointer p){
    printf(" %d", p->ndkey);
    if(p->Left != NULL) preO(p->Left);
    if(p->Right != NULL) preO(p->Right);
}

void i_order(NodePointer p){
        if(p->Left != NULL) i_order(p->Left);
        printf(" %d", p->ndkey);
        if(p->Right != NULL) i_order(p->Right);
}

int main(){

   int i,m,n;
   char O[10];

   scanf("%d",&m);

   for(i=0;i<m;i++){
       scanf("%s",O);

       if(O[0]=='i'){
           scanf("%d",&n);
           insert(n);
       }

       else if(O[0]=='p'){
           i_order(root);
           printf("\n");
           preO(root);
           printf("\n");
        }
    }
    return 0;
}