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



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

void insert(int);
void inorder(node);
void preorder(node);


node root;

int main() {
  int i,k,m;
  char command[20];

  scanf("%d",&m);
  for(i=0;i<m;i++){

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

  return 0;
}

void insert(int k) {
  node x=root;
  node y=NULL;
  node z;
  z=(node)malloc(sizeof(node));
  z->key=k;
  z->left=NULL;
  z->right=NULL;
  while(x!=NULL){
    y=x;
    if(z->key<x->key) x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NULL) root=z;
  else if(z->key<y->key) y->left=z;
  else y->right=z;
}

void inorder(node z) {
  if(z!=NULL){
   
    inorder(z->left);
    printf(" %d",z->key);
    inorder(z->right);
    
  
  }
  

}

void preorder(node z) {
  if(z!=NULL) {
    printf(" %d",z->key);
    preorder(z->left);
    preorder(z->right);
    
  }
}