#include <stdio.h>
#include <stdlib.h>
#define NIL NULL

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

Node *T;

void insert(int);
void print(Node *);
void inorder(Node *);
void preorder(Node *);

int main()
{
  int n,i,k,j;
  char command[10];
  Node *z;

  //T->l=NIL;
  //T->r=NIL;
  
  scanf("%d",&n);
  if(n>500000) exit(1);
  for(i=0;i<n;i++){
      scanf("%s",command);
    if(command[0] == 'i'){
      scanf("%d",&k);
      insert(k);
    }
    else
      print(T);
  }
  return 0;
}

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

  y = NIL; //xの親
  x = T;

  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  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;
  
  if(y==NIL) //Tが空の場合
    T = z;
  else if(z->key < y->key)
    y->l = z; //zをyの左の子にする
  else
    y->r = z; //zをyの右の子にする
  //printf(" %d",x->p);
}

void print(Node *root)
{
  if(root==NIL) return;
  
  inorder(root); //左→上→右
  printf("\n");
  preorder(root); //左→右→上
  printf("\n");
}

void inorder(Node *root)
{
  if(root==NIL) return;
  inorder(root->l);
  printf(" %d",root->key);
  inorder(root->r);
}

void preorder(Node *root)
{
  if(root==NIL) return;
  printf(" %d",root->key);
  preorder(root->l);
  preorder(root->r);
}

