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

struct Node{
  int data;
 struct Node *parent, *left, *right;
};

struct Node *root;

void insert(int x){
  struct Node *root_tmp = root;
  struct Node *elem;
  struct  Node *prev = NULL;
  elem = (struct Node *)malloc(sizeof(struct Node));
  elem->data = x;
  elem->left = NULL;
  elem->right = NULL;
  

  while(root_tmp != NULL){
    prev = root_tmp;
    if(elem->data < root_tmp->data){
      root_tmp = root_tmp->left;
    }else{
      root_tmp = root_tmp->right;
    }
  }

  elem->parent = prev;

  if(elem->parent == NULL){
    root = elem;
  }else{
    if(elem->parent->data < elem->data){
      elem->parent->right = elem;
    }else{
      elem->parent->left = elem;
    }
  }
}
int Preorder(struct Node *root){
  if(root == NULL) return -1; 
  printf(" %d",root->data);
  Preorder(root->left);
  Preorder(root->right);
  return 0;
}

int Inorder(struct Node *root){
  if(root==NULL) return -1;
  Inorder(root->left);
  printf(" %d",root->data);
  Inorder(root->right);
  return 0;
}

int main(){
  int n,elem,i;
  char c[10];
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",c);
    if(strcmp(c,"insert")==0){
      scanf("%d",&elem);
      insert(elem);
    }else{
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }
  }
  return 0;
}