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

typedef struct _node {
	signed int key;
	struct _node *left;
	struct _node *right;
} node;

node *allocNode(int key) {
	node *p = (node *)malloc(sizeof(node));
	p->key = key;
	p->left = NULL;
	p->right = NULL;
	return p;
}

void terminate(node *p) {
	if (p == NULL) return;
	terminate(p->left);
	terminate(p->right);
	free(p);
}
void insert(node **T, node *z) {
	node *y = NULL;
	node *x = *T;
	while (x != NULL) {
		y = x;
		if (z->key < x->key) x = x->left;
		else x = x->right;
	}
	if (y == NULL) *T = z;
	else if (z->key < y->key) y->left = z;
	else y->right = z;
}

void preParse(node *p) {
	if (p == NULL) return;
	printf(" %d",p->key);
	preParse(p->left);
	preParse(p->right);
}
void inParse(node *p) {
	if (p == NULL) return;
	inParse(p->left);
	printf(" %d",p->key);
	inParse(p->right);
}

int main() {
	int n, i, key;
	char order[7];
	node *p, *root = NULL;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s %d", order, &key);
		switch (order[0])
		{
		case 'i':
			p = allocNode(key);
			insert(&root, p);
			break;
		case 'p':
			inParse(root);
			printf("\n");
			preParse(root);
			printf("\n");
			break;
		}
	}
	terminate(root);
	return 0;
}

