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

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

typedef struct node * Node;

Node root,NIL;
int maxh;

void insert(int x){
  int H;
  Node b=NIL;
  Node a = root;
  Node c;

  c = malloc(sizeof(struct node));
  c->key =x;
  c->left = NIL;
  c->right = NIL;

  while(a!=NIL){
    b=a;
    if(c->key < a->key){
      a = a->left;
    }
    else{
      a = a->right;
    }
  }

  c ->parent = b;

  if(b ==NIL){
    root =c;
  }
  else{
    if(c->key < b->key){
      b->left =c;
    }
    else{
      b->right =c;
    }
  }
}
 
void inorder(Node x){
  if(x == NIL){
    return;
  }
  inorder(x->left);
  printf(" %d",x->key);
  inorder(x->right);
}
void preorder(Node x){
  if( x ==NIL) {
    return;
  }
  printf(" %d",x->key);
  preorder(x->left);
  preorder(x->right);
}

int main(){
  int i,num,x;
char com[20];
scanf("%d",&num);
maxh=0;
for(i=0;i<num;i++){
  scanf("%s",com);
  if(strcmp(com,"insert")==0){
    scanf("%d",&x);
    insert(x);
  }
  else if(strcmp(com,"print")==0){
    inorder(root);
    printf("\n");
    preorder(root);
    printf("\n");
  }
 }
return 0;
}

