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

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

typedef struct node * binary;

binary root;

void insert(int k){
  binary y=NIL;
  binary x=root;
  binary z;

  z=malloc(sizeof(struct 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)
    root=z;
  else if(z->key<y->key)
    y->l=z;
  else
    y->r=z;
}


void inorder(binary p){

  if(p->l!=NIL)
    inorder(p->l);

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

  if(p->r!=NIL)
    inorder(p->r);

}
void preorder(binary p){

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

  if(p->l!=NIL)
    preorder(p->l);

  if(p->r!=NIL)
    preorder(p->r);

}


int main(){
  int n,i,k;
  char a[10];

  scanf("%d",&n);

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

    if(a[0]=='i'){
      scanf("%d",&k);
      insert(k);
    }
    else if(a[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}