#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;
const int SIZE = 10005;

struct BSTNode
{
	int key;
	BSTNode *lchild, *rchild;
	BSTNode(int k = 0, BSTNode* l = nullptr, BSTNode* r = nullptr)
		:key(k), lchild(l), rchild(r){}
};
typedef BSTNode* BSTree;
BSTree insert(BSTree& T, int key)
{
	if (!T)
	{
		T = new BSTNode(key);
		return T;
	}
	else if (key > T->key)
		T->rchild = insert(T->rchild, key);
	else
		T->lchild = insert(T->lchild, key);
	return T;
}

void pre_order(const BSTree T)
{
	if (!T)
		return;
	cout << ' ' << T->key;
	pre_order(T->lchild);
	pre_order(T->rchild);
}

void in_order(const BSTree T)
{
	if (!T)
		return;
	
	in_order(T->lchild);
	cout << ' ' << T->key;
	in_order(T->rchild);
}
int main(void)
{
	ios::sync_with_stdio(false);
	int n, key;
	int Tsize;
	char str[10];
	cin >> n;
	BSTree T = nullptr;
	while (n--)
	{
		cin >> str;
		if (str[0] == 'i')
		{
			cin >> key;
			insert(T, key);
		}
		else
		{
			in_order(T);
			cout << endl;
			pre_order(T);
			cout << endl;
		}
	}
	return 0;
}