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

struct node{
    struct node *right;
    struct node *left;
    struct node *p;
    int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

/* Node treeMinimum(Node x){
   while(x->left != NIL) {
   x = x->left;
   }
   return x;
   } */

/* Node treeSearch(Node x, int k){
   while(x != NIL && k != x->key) {
   if(k < x->key){
   x = x->left;
   }
   else {
   c = x->right;
   }
   return x;
   }

   Node treeSuccessor(Node x){
   Node y;

   if(x->right != NIL){
   return treeMinimum(x->right);
   }
   y = x->p;
   while(y != NIL && x == y->right) {
   x = y;
   y = y->p;
   }
   return y;
   }
   */
/*    void treeDelete(Node z){
      Node y; // node to be deleted
      Node x; // child of y
      if(z->left == NIL || z->right == NIL) {
      y = z;
      }
      else {
      y = treeSuccessor(z);
      }
      if(y->left != NIL) {
      x = y->right;
      }
      else {
      x = y->right;
      }
      if(x != NIL) {
      x->p = y->p;
      }
      if(y->p == NIL) {
      T->root = x;
      }
      else if(y == y->p->left) {
      y->p->left = x;
      }
      else {
      y->p->right = x;
      }
      } */

void insert(int k){
    Node y = NIL;
    Node x = root;
    Node z;

    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->p = y;
    if(y == NIL) {
        root = z;  
    }
    else if(z->key < y->key){
        y->left = z;
    }
    else y->right = z;
}

void inorder(Node x){
    if(x->left != NIL){
        inorder(x->left);
    }

    printf(" %d",x->key);
    if(x->right != NIL){
        inorder(x->right);
    }

}

void preorder(Node x){
    printf(" %d",x->key);
    if(x->left!= NIL){
        preorder(x->left);
    }

    if(x->right!= NIL){
        preorder(x->right);
    }
}

int main(){
    int n, i, x;
    char com[20];
    scanf("%d", &n);

    for ( i = 0; i < n; i++ ){
        scanf("%s", com);
        /*  if ( com[0] == 'f' ){
            scanf("%d", &x);
            Node t = treeSearch(root, x);
            if ( t != NIL ) printf("yes\n");
            else printf("no\n");
            } else */ 
        if ( com[0] == 'i' ){
            scanf("%d", &x);
            insert(x);
        } else if ( com[0] == 'p' ){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        } /*else if ( com[0] == 'd' ){
            scanf("%d", &x);
            treeDelete(treeSearch(root, x));
            } */
    }
    return 0;
}