#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(int);
void inorder(Node);
void preorder(Node);
void maxHeapify(int *,int);

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;
  }


  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);
  }

