

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

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

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

Node *T = NULL;


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

  scanf("%d", &in);


  for(i=0 ; i<in ; i++){
    scanf("%s", s);

    if(s[0]=='i'){
      temp =malloc(sizeof(Node));
      scanf("%d",&(temp->key));
      temp->left = NULL;
      temp->right = NULL;
      insert(temp);
    }
    else{
      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 *n){
  Node *x,*y;

  y = NULL;
  x = T;

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

  n->parent = y;

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

}