#include <stdio.h>
#include <stdlib.h>

struct node {
	int key;
	struct node *car;
	struct node * cdr;
};

void
record(struct node *r, struct node *p)
{
	if (p->key == r->key)
		return;
	else if (p->key < r->key) {
		if (r->car == NULL)
			r->car = p;
		else
			record(r->car, p);
	} else {
		if (r->cdr == NULL)
			r->cdr = p;
		else
			record(r->cdr, p);
	}
}

void
preorder(struct node *a)
{
	if (a == NULL)
		return;

	printf(" %d", a->key);
	preorder(a->car);
	preorder(a->cdr);
}

void
inorder(struct node *a)
{
	if (a == NULL)
		return;

	inorder(a->car);
	printf(" %d", a->key);
	inorder(a->cdr);
}

int
main(void)
{
	int i, n, p;
	struct node *a;

	scanf("%d", &n);

	a = (struct node *)malloc(sizeof(struct node) * n);
	if (a == NULL)
		return 1;

	for (i = p = 0; i < n; i++) {
		char cmd[16];
		int key;

		scanf("%s", cmd);
		if (cmd[0] == 'i') {
			scanf("%d", &key);
			a[p].key = key;
			a[p].car = NULL;
			a[p].cdr = NULL;
			record(a, a + p++);
		} else if (cmd[0] == 'p') {
			inorder(a);
			printf("\n");
			preorder(a);
			printf("\n");
		}
	}

	return 0;
}

