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







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



struct node *Tree,*END;
int number;


void input(void){
  char str[50];
  int n;
  int i;
  char str1[50]="insert";
  char str2[50]="print";

  
  scanf("%d",&number);


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

  
    
    scanf("%s",str);
    if(strcmp(str,str1)==0){
      
      scanf("%d",&n);

      
      insert(n);
      
    }


    else if(strcmp(str,str2)==0){
	Inorder(Tree);
	printf("\n");
	Preorder(Tree);
	printf("\n");
      }
  }

}


  void insert(int n){

    struct node *a=Tree;
    struct node *b=END;
    struct node *c;


    c->me=c;
    c->left=END;
    c->right=END;

    while(b!=END){

      b=a;
      if(c->me <a->me){
	a=a->left;
	

      }else{a=a->right;}
    }

    
      c->parent=b;
      if(b==END){
	Tree=c;
      }else {
	if(c->me < b->me){
	  b->left=c;
	}else{
	  b->right=c;
	}
      }
   
  }


  void Inorder(struct node *a){
    if(a==END)return;
    Inorder(a->left);
    printf("%d ",a->me);
    Inorder(a->right);
    
  }


  void Preorder(struct node *a){
    if(a==END)return;
    printf("%d",a->me);
    Preorder(a->left);
    Preorder(a->right);
  }

  int main(void){
    input();

    return 0;
  }

