#include <stdio.h>
#include <malloc.h>
#define NIL -1

typedef struct t{
	int r;
	int l;
	int k;
}node;
node T[500000];
int s;
void view(void);
void inorder(int);
void preorder(int);
void insert(int k) {
int p = 0;
	while (1) {
		if (k < T[p].k) {
			if (T[p].l == NIL) {
				T[p].l = s;
				T[s++].k = k;
				break;
			}
			else p = T[p].l;
		}
		else {
			if (T[p].r == -1) {
				T[p].r = s;
				T[s++].k = k;
				break;
			}
			else p = T[p].r;
		}
	}
}
int main() {
	int i, x,root,n;
	char com[20];
	scanf("%d", &n);
	for (i = 0; i < n; i++) T[i].k = T[i].l = T[i].r = -1;
	s = 0;
	for (i = 0; i < n; i++) {
		scanf("%s", com);
		if (com[0] == 'i') {
			scanf("%d", &x);
			if (i == 0) {
				root = x;
				T[s++].k = x;
			}
			else {
				insert(x);
			}
		}
		else if (com[0] == 'p') {
			inorder(0);
			printf("\n");
			preorder(0);
			printf("\n");
		}
	}

	return 0;
}
void inorder(int z) {
	if (T[z].l != NIL) {
		inorder(T[z].l);
	}
	printf(" %d",T[z].k);
	if (T[z].r != NIL) {
		inorder(T[z].r);
	}
}
void preorder(int z) {
	printf(" %d", T[z].k);
	if (T[z].l != NIL) {
		preorder(T[z].l);
	}
	if (T[z].r != NIL) {
		preorder(T[z].r);
	}
}
