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

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

struct Tree{
  struct node *root;
};

typedef struct node Node;

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

Node *NIL;

  
int main(){

  int n,i,num;
  char order[7];
  Node *root;

  //root=NIL;

  //root=(Node*)malloc(sizeof(Node));

  //NIL->right=NULL;
  //printf("wa-i30\n");
  //NIL->left=NULL;
  //NIL->parent=NULL;
  //NIL->key=-1;

  //printf("wa-i20\n");
  
  root=NIL;
 
  scanf("%d",&n);

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

    scanf("%s %d",order,&num);
    
    //printf("%s\n",order);

    // root->key=3;

    if(strcmp(order,"insert")==0){
      
      //printf("wa-i\n");
      //printf("%d\n",root->key);
      insert(&root,num);
      //printf("Main : address of root;%p\n",root);
      // printf("%d\n",root->key);

    }
    
    else if(strcmp(order,"print")==0){
      //printf("%d\n",root->key);

      
      inorder(root);
      
      printf("\n");
	     
      preorder(root);

      printf("\n");

    }

  }

  return 0;
}

void insert(Node** root,int num){

  Node *x,*y,*z;

  y=NIL;
  x=*root;

  //printf("address of root;%p\n",root);

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

  z->left=NIL;
  z->right=NIL;
  z->key=num;

  //printf("%d\n",z->key);  

  while(x!=NIL){
    y=x;
    if( z->key < x->key )x=x->left;
    else x=x->right;
    //printf("wa-i200\n");
  }
    
  z->parent=y;
  
  if(y==NIL){
    *root=z;
    //printf("wa-i100\n");
  }
  else if( z->key < y->key ) y->left=z;
  else y->right=z;

  //printf("%d\n",(*root)->key);
  //printf("%d\n",z->key);
  // printf("address of root;%p\n",root);
  
}

void preorder(Node *u){
  
  if(u==NIL) return;

  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
  
}

void inorder(Node *u){

  if(u==NIL) return;
  
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);

}