#include <stdio.h>
#include <stdlib.h>
#define NIL NULL
struct node {
	struct node *p;
	struct node *l;
	struct node *r;
	int k;
};
typedef struct node* Node;
Node Root;
void insert(int);
void preorder();
void inorder();
int main() {
	Root->k = -1;
	Root->l = NIL;
	Root->r = NIL;
	Root->p = NIL;
	int n, i, k;
	char w[10];
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", w);
		if (w[0] == 'i') {
			scanf("%d", &k);
			insert(k);
		} /*else if (w[0] == "f") {
		 scanf("%d", &k);
		 find(k);
		 }*/else {
			inorder(Root);
			preorder(Root);
		}
	}
	return 0;
}

void insert(int n) {
	Node x = malloc(sizeof(struct node));
	Node y;
	Node z;
	x->k = n;
	x->l = NIL;
	x->r = NIL;
	x->p = NIL;
	if (Root->r == NIL) {
		Root->r = x;
	} else {
		y = Root->r;
		while (y != NIL) {
			if (y->k > x->k) {
				z = y->l;
				y = z;
			} else {
				z = y->r;
				y = z;
			}
		}
		x = y;
	}
}
void inorder() {
	if (Root != NIL) {
		inorder(Root->l);
		printf(" %d", Root->k);
		inorder(Root->r);
	}
}

void preorder(){
	if (Root != NIL) {
		printf(" %d", Root->k);
		preorder(Root->l);
		preorder(Root->r);
	}
}