#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
  struct Node *parent;
  struct Node *left;
  struct Node *right;
  int key;
} node;
void preOrder(node *);
void inOrder(node *);
void insert(int);
node *root;
int n;
int main() {
  int i, j, key;
  char command[7];
 
  scanf("%d", &n);
  for (i = 0; i < n; i++) {    
    scanf("%s", command);
    if ('i' == command[0]) {
      scanf("%d", &key);
      insert(key);
    } else {
      inOrder(root);
      printf("\n");
      preOrder(root);
      printf("\n"); 
    }
  }
  return 0;
}
void inOrder(node *u) {
  if (u == NULL) {
    return ;
  }
  if (u->left != NULL) inOrder(u->left);
  printf(" %d",u->key);
  if (u->right != NULL) inOrder(u->right);
  return ;
}
void preOrder(node *u) {
  if (u == NULL) {
    return ;
  }
  printf(" %d",u->key);
  if (u->left != NULL) preOrder(u->left);
  if (u->right != NULL) preOrder(u->right);
  return ;
}
void insert(int key) {
  node *y = NULL;
  node *x = root;
  node *z;
 
  z = (node*) malloc(sizeof(node));
  z->left = NULL;
  z->right = NULL;
  z->key = key;
 
  while (x != NULL) {
    y = x;
    if (key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if ( y==NULL ) {
    root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
  return ;
}

