#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define N 500001
#define NIL NULL
 
void insert(int);
void Preorder(Node );
void Inorder(Node );
 
struct node{
    int key;
    struct node *parent;
    struct node *left;
    struct node *right;
};
 
typedef struct node *Node;
 
Node root;
 
int main ()
{
    int n,i,x;
    char s[10];
 
    scanf("%d",&n);
 
    for(i=0;i<n;i++){
        scanf("%s",s);
        if(strcmp(s,"insert")==0){
            scanf("%d",&x);
            insert(x);
        }
        else if(strcmp(s,"print")==0){
            Inorder(root);
            printf("\n");
            Preorder(root);
            printf("\n");
        }
    }
 
    return 0;
}
 
void insert(int k){
    Node z;
    Node y=NIL;
    Node x=root;
 
    z=malloc(sizeof(struct node));
    z->key=k;
    z->left=NIL;
    z->right=NIL;
 
    while(x!=NIL){
        y=x;
        if(z->key < x->key) x=x->left;
        else x=x->right;
    }
 
    z->parent=y;
 
    if(y==NIL) root=z;
    else if(z->key < y->key) y->left=z;
    else y->right=z;
}
 
void Preorder(Node u){
    if(u!=NIL){
    printf(" %d",u->key);
    if(u->left != NIL) Preorder(u->left);
    if(u->right != NIL) Preorder(u->right);
    }
}
 
void Inorder(Node u){
    if(u!=NIL){
        Inorder(u->left);
        printf(" %d",u->key);
        Inorder(u->right);
    }
}