#include<stdio.h>
#include<stdlib.h>
#define NIL NULL

struct node{
  int key;
  struct node *parent;
  struct node *left;
  struct node *right;
};

typedef struct node *Node;

Node root;

void insert(k){
     Node w;
     Node y = NIL; // x の親
     Node x = root;


     w = malloc(sizeof(struct node));
     w->key = k;
     w->right = NIL;
     w->left = NIL;

     while(x != NIL){
       y = x;
       // 親を設定
       if(w->key < x->key){
         x = x->left;
       }
      // 左の子へ移動
       else{
         x = x->right;
       }
     }
     // 右の子へ移動
     w->parent = y;

    if(y == NIL){ // T が空の場合
        root = w;
    }
    else if(w->key < y->key){
        y->left = w;
    }
     // z を y の左の子にする
    else{
        y->right = w;
    } // z を y の右の子にする
}

void inorder(Node u){
  if(u == NIL){
    return;
  }
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}

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


int main(){
  int i,m,n;
  char co[20];

  scanf("%d",&m);
  for (i = 0 ; i < m ; i++){
    scanf("%s", co);
    if(co[0] == 'i'){
       scanf("%d", &n);
       insert(n);
     }
     else if(co[0] == 'p'){
       inorder(root);
       printf("\n");
       preorder(root);
       printf("\n");
     }
   }

   return 0;
  }

