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

#define NIL NULL

typedef struct node{
  int key;
  struct node *l;
  struct node *r;
  struct node *p;
} Node;

typedef struct node* NodePointer;
 
NodePointer root;

void insert(int key){

  NodePointer x, y, z;

  y = NIL;
  x = root;

  z = malloc(sizeof(struct node));
  z->key = key;
  z->l = NIL;
  z->r = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) x = x->l;
    else x = x->r;
    z->p = y;
  }

  z->p = y;

  if(y == NIL) root = z;
  else if(z->key < y->key) y->l = z;
  else y->r = z;

}

void inorder(NodePointer t){

  if(t->l != NIL) inorder(t->l);
  printf(" %d", t->key);
  if(t->r != NIL) inorder(t->r);

}

void preorder(NodePointer t){
 
  printf(" %d", t->key);
  if(t->l != NIL) preorder(t->l);
  if(t->r != NIL) preorder(t->r);

}

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

  return 0;

}