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

typedef struct treeNode{
  int key;
  struct treeNode *p;
  struct treeNode *left;
  struct treeNode *right;
}Node;

void printPreorder(Node *);
void printInorder(Node *);
void insert(Node *);

Node *T = NULL;

int main(){
  int m, i, root, k;
  Node *temp;
  char s[7];

  scanf("%d", &m);

  for(i=0; i<m; i++){
    scanf("%s", s);
    //printf("%s\n", s);
    if(s[0] == 'i'){
      temp = malloc(sizeof(Node));
      scanf("%d", &(temp->key));
      temp->left = NULL;
      temp->right = NULL;
      insert(temp);
      //printf("i = %d m = %d\n",i,m);
      //fflush(stdout);
    }else{
      printf("%d\n",i);
      printInorder(T);
      printf("\n");
      printPreorder(T);
      printf("\n");
    }
  }
  
  return 0;
}

void printPreorder(Node *N){
  printf(" %d", N->key);

  if(N->left != NULL){
    printPreorder(N->left);
  }

  if(N->right != NULL){
    printPreorder(N->right);
  }

}

void printInorder(Node *N){

  if(N->left != NULL){
    printInorder(N->left);
  }

  printf(" %d", N->key);

  if(N->right != NULL){
    printInorder(N->right);
  }

}

void insert(Node *z){
  Node *x, *y;

  y = NULL; // xの親
  x = T;

  while(x != NULL){
    y = x;
    if(z->key < x->key){
      x = x->left;
    }else{
      x = x->right;
    }
  }

  z->p = y;
  
  if( y == NULL){
    T = z;
  }else if(z->key < y->key){
    y->left = z;
  }else{
    y->right = z;
  }

}