#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100000

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

struct node *root,*NIL;

void insert(int k){
  struct node *y = NIL,*x = root,*z;

  z = (struct node *)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->parent = y;

  if(y == NIL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;
}

void inorder(struct node *v){
  if(v == NIL)return;
  inorder(v->left);
  printf(" %d",v->key);
  inorder(v->right);
}

void preorder(struct node *v){
  if(v == NIL)return;
  printf(" %d",v->key);
  preorder(v->left); 
  preorder(v->right);
}

int main(){
  int m,k;
  int i = 0;
  char com[10];
  
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%s",com);
    if(strcmp(com,"insert") == 0){
      scanf("%d",&k);
      insert(k);
    }
    else if(strcmp(com,"print") == 0){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;  
}

