#include <stdio.h>
#include <stdlib.h>
 
struct node{
  struct node *parent;
  struct node *l;
  struct node *r;
  int key;
};
typedef struct node * Node;
 
#define NIL NULL
Node root;

void Insert(int k){
Node p = NIL;
Node q = root;
Node z;

z = malloc(sizeof(struct node));
z->key = k;
z->l = NIL;
z->r = NIL;

while(q != NIL){
p = q;
if(z->key < q->key){
q = q->l;
}
 else {
q = q->r;
}
}
z->parent = p;

if(p == NIL){
root = z;
}
 else if(z->key < p->key){
p->l = z;
}
 else {
p->r = z;
}
}

void Inorder(Node u){
if(u->l != NIL){
Inorder(u->l);
}
printf(" %d",u->key);

if(u->r != NIL){
Inorder(u->r);
}
}

void Preorder(Node u){
printf(" %d",u->key);
if(u->l != NIL){
Preorder(u->l);
}
if(u->r != NIL){
Preorder(u->r);
}
}

int main(void){
int n,i,x;
char com[20];

scanf("%d",&n);

root = malloc(sizeof(struct node));
root = NIL;

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

if(com[0] == 'i'){
scanf("%d",&x);

Insert(x);
}
 else {            
Inorder(root);
printf("\n");
Preorder(root);
printf("\n");
}
}
return 0;
}