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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

#define NIL NULL

Node root;

void ins(int);
void ino(Node);
void pre(Node);

int main(){
  int k,i,x;
  char c[20];
  scanf("%d",&k);

  for(i = 0 ; i < k ; i++ ){

    scanf("%s", c);

    if(c[0] == 'i'){

      scanf("%d", &x);
      ins(x);

    }

    else if (c[0] == 'p'){
      ino(root);
      printf("\n");
      pre(root);
      printf("\n");
    }
  }

  return 0;
}
void ins(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = (Node)malloc(sizeof(struct node));
  z->key = k;
  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 ino(Node u){

  if(u->left != NIL)

    ino(u->left);

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

  if(u->right != NIL)

    ino(u->right);

}

void pre(Node u)
{

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

  if(u->left != NIL)

    pre(u->left);

  if(u->right != NIL)

    pre(u->right);

}