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

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

Node *root,*NIL;

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

  z = (Node *)malloc(sizeof(Node));

  y = NIL;
  x = root;

  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 printi(Node *a){
  if(a == NIL)
    return;

  printi(a->left);
  printf(" %d", a->key);
  printi(a->right);
}

void printp(Node *a){
  if(a == NIL)
    return;

  printf(" %d", a->key);
  printp(a->left);
  printp(a->right);
}

int main(){
  int n,i;
  Node *a;
  char *s[7];

  a = (Node *)malloc(sizeof(Node));

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%s", s[7]);

    if(strcmp(*s, "insert") == 0){
      scanf("%d", &a->key);
      insert(a);
    }

    else if(strcmp(*s, "print") == 0){
      printi(root);
      printf("\n");
      printp(root);
      printf("\n");
    }
  }

  return 0;
}