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


typedef struct tree_t{
	int key;
	struct tree_t *left;
	struct tree_t *right;
}TREE_T;

TREE_T *TREE;


void insert(TREE_T *z)
{
	TREE_T *y = NULL;	// x の親
	TREE_T *x = TREE;	// 木の根

	while(x != NULL){
		y = x;	// 親を設定
		if(z->key < x->key)
			x = x->left;	// 左の子へ移動
		else
			x = x->right;	// 右の子へ移動
	}

	if (y == NULL)	// T が空の場合
		TREE = z;	// Tの根 = z
	else if(z->key < y->key)
		y->left = z; // z を y の左の子にする
	else
		y->right = z; // z を y の右の子にする
}

int WALK_COUNT;

// kind = 0 : 通りがけ　1 : 行きがけ
void Walk_tree(TREE_T *p, int kind)
{
	if(kind == 1)
		printf(" %d", p->key);

	if(p->left != NULL)
		Walk_tree(p->left, kind);

	if(kind == 0)
		printf(" %d", p->key);

	if(p->right != NULL)
		Walk_tree(p->right, kind);
}


int main()
{
	TREE_T *p;
	int n;
	char command[10];
	int num;
	int i;

	scanf("%d", &n);

	TREE = NULL;

	for(i = 0; i < n; i++){
		scanf("%s", command);
		if(!strcmp(command, "print")){
			// 木をなぞる
			Walk_tree(TREE, 0);
			printf("\n");
			Walk_tree(TREE, 1);
			printf("\n");
		}else{
			scanf("%d", &num);
			p = (TREE_T *)malloc(sizeof(TREE_T));
			p->key = num;
			p->left = NULL;
			p->right = NULL;
			insert(p);
		}
	}

	return 0;
}
