#include <iostream>
#include <queue>

class RedBlackTree{
public:
	class Node{
	public:
		bool Color;
		int Key;
		Node *Left, *Right, *Parent;
		Node(int k){
			Color = false; // true <-> red, false <-> black
			Key = k;
			Left = Right = Parent = nullptr;
		}
	};

	Node *Root, *NIL;

	RedBlackTree(){
		NIL = new Node(0);
		Root = NIL;
	}

	void LeftRotate(Node *x){
		Node *y = x->Right;
		x->Right = y->Left;
		if(y->Left != NIL) y->Left->Parent = x;
		y->Parent = x->Parent;
		if(x->Parent == NIL) Root = y;
		else if(x == x->Parent->Left) x->Parent->Left = y;
		else x->Parent->Right = y;
		y->Left = x;
		x->Parent = y;
	}

	void RightRotate(Node *x){
		Node *y = x->Left;
		x->Left = y->Right;
		if(y->Right != NIL) y->Right->Parent = y;
		y->Parent = x->Parent;
		if(x->Parent == NIL) Root = y;
		else if(x == x->Parent->Left) x->Parent->Left = y;
		else x->Parent->Right = y;
		y->Right = x;
		x->Parent = y;
	}

	void Insert(int v){
		Node *z = new Node(v);
		z->Color = true;
		z->Left = z->Right = z->Parent = NIL;
		Node *y = NIL;
		Node *x = Root;
		while(x != NIL){
			y = x;
			if(z->Key < x->Key) x = x->Left;
			else x = x->Right;
		}
		z->Parent = y;
		if(y == NIL) Root = z;
		else if(z->Key < y->Key) y->Left = z;
		else y->Right = z;
//		InsertFixup(z);
	}

	void InsertFixup(Node *z){
		while(z->Parent->Color == true){
			if(z->Parent == z->Parent->Parent->Left){
				Node *y = z->Parent->Parent->Right;
				if(y->Color == true){
					z->Parent->Color = false;
					y->Color = false;
					z->Parent->Parent->Color = true;
					z = z->Parent->Parent;
				}else{
					if(z == z->Parent->Right){
						z = z->Parent;
						LeftRotate(z);
					}
					z->Parent->Color = false;
					z->Parent->Parent->Color = true;
					RightRotate(z->Parent->Parent);
				}
			}else{
				Node *y = z->Parent->Parent->Left;
				if(y->Color == true){
					z->Parent->Color = false;
					y->Color = false;
					z->Parent->Parent->Color = true;
					z = z->Parent->Parent;
				}else{
					if(z == z->Parent->Left){
						z = z->Parent;
						RightRotate(z);
					}
					z->Parent->Color = false;
					z->Parent->Parent->Color = true;
					LeftRotate(z->Parent->Parent);
				}
			}
		}
		Root->Color = false;
	}

	void InorderTreeWalk(Node *x, std::queue<int> &q){
		if(x == NIL) return;
		InorderTreeWalk(x->Left, q);
		q.push(x->Key);
		InorderTreeWalk(x->Right, q);
	}

	void PreorderTreeWalk(Node *x, std::queue<int> &q){
		if(x == NIL) return;
		q.push(x->Key);
		PreorderTreeWalk(x->Left, q);
		PreorderTreeWalk(x->Right, q);
	}
};

int main(){
//	std::cin.tie(0);
//	std::ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	RedBlackTree rbt;
	while(n--){
		std::string s;
		std::cin >> s;
		if(s == "insert"){
			int t;
			std::cin >> t;
			rbt.Insert(t);
//			std::queue<int> q;
/*			rbt.InorderTreeWalk(rbt.Root, q);
			while(!q.empty()){
				std::cout << " ";
				std::cout << q.front();
				q.pop();
				if(q.empty()) std::cout << "\n";
			}
			rbt.PreorderTreeWalk(rbt.Root, q);
			while(!q.empty()){
				std::cout << " ";
				std::cout << q.front();
				q.pop();
				if(q.empty()) std::cout << "\n";
			}
*/		}else{
			std::queue<int> q;
			rbt.InorderTreeWalk(rbt.Root, q);
			while(!q.empty()){
				std::cout << " ";
				std::cout << q.front();
				q.pop();
				if(q.empty()) std::cout << "\n";
			}
			rbt.PreorderTreeWalk(rbt.Root, q);
			while(!q.empty()){
				std::cout << " ";
				std::cout << q.front();
				q.pop();
				if(q.empty()) std::cout << "\n";
			}
		}
	}
}


Measured memory_bytes: 28492