#include <stdio.h>
#include <stdlib.h>
struct Node{
	int key;
	struct Node *right, *left,*parent;
};

struct Node *root,*nil;

void insert(int k){
	struct Node *y=nil;
	struct Node *x=root;
	struct Node *z;
	z=(struct Node*)malloc(sizeof(struct Node));
	z->key=k;
	z->left=nil;
	z->right=nil;
	
	while(x!=nil){
		y=x;
		if(z->key<x->key){
			x=x->left;
		}
		else{
			x=x->right;
		}
	}	
	
	z->parent=y;
	if(y==nil){
		root=z;
	}
	else{
		if(z->key<y->key){
			y->left=z;
		}
		else {
			y->right=z;
		}
	}
}

void inorder(struct Node *u){
	if(u==nil){
		return;
	}
	inorder(u->left);
	printf(" %d",u->key);
	inorder(u->right);
}

void preorder(struct Node *u){
	if(u==nil){
		return;
	}
	
	if(u==nil){
		return;
	}
	printf(" %d",u->key);
	preorder(u->left);
	preorder(u->right);
}

int main(void){
	int n,i,x;
	scanf("%d",&n);
	int d;
	char string[10];
	
	for(i=0;i<n;i++){
		scanf("%s %d",string,&d);
		if(string[0]=='i'){
			insert(d);
		}
		else if(string[0]=='p'){
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}
	
	return 0;
}
