#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

class redblack_tree{
public:
	class node{
	public:
		bool red;
		Int key;
		node *left, *right, *parent;
		node(Int k){
			red = false; // true <-> red, false <-> black
			key = k;
			left = right = parent = nullptr;
		}
	};

	node *root, *NIL;
	size_t size;

	redblack_tree(){
		NIL = new node(0);
		root = NIL->parent = NIL->right = NIL->left = NIL;
		size = 0;
	}

	void left_rotate(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 right_rotate(node *x){
		node *y = x->left;
		x->left = y->right;
		if(y->right != NIL) y->right->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->right = x;
		x->parent = y;
	}

	node *insert(Int v){
		node *y = NIL;
		node *x = root;
		while(x != NIL){
			y = x;
			if(x->key == v) return x;
			if(v < x->key) x = x->left;
			else x = x->right;
		}
		++size;
		node *z = new node(v);
		z->red = true;
		z->left = z->right = z->parent = NIL;
		z->parent = y;
		if(y == NIL) root = z;
		else if(z->key < y->key) y->left = z;
		else y->right = z;
//		insert_fixup(z);
		return z;
	}

	void insert_fixup(node *z){
		while(z->parent->red){
			if(z->parent == z->parent->parent->left){
				node *y = z->parent->parent->right;
				if(y->red){
					z->parent->red = false;
					y->red = false;
					z->parent->parent->red = true;
					z = z->parent->parent;
				}else if(z == z->parent->right){
					z = z->parent;
					left_rotate(z);
				}else{
					z->parent->red = false;
					z->parent->parent->red = true;
					right_rotate(z->parent->parent);
				}
			}else{
				node *y = z->parent->parent->left;
				if(y->red){
					z->parent->red = false;
					y->red = false;
					z->parent->parent->red = true;
					z = z->parent->parent;
				}else if(z == z->parent->left){
					z = z->parent;
					right_rotate(z);
				}else{
					z->parent->red = false;
					z->parent->parent->red = true;
					left_rotate(z->parent->parent);
				}
			}
		}
		root->red = false;
	}

	void transplant(node *u, node *v){
		if(u->parent == NIL) root = v;
		else if(u == u->parent->left) u->parent->left = v;
		else u->parent->right = v;
		v->parent = u->parent;
	}

	void delete_node(node *z){
		node *x = NIL;
		node *y = z;
		bool y_originally_red = y->red;
		if(z->left == NIL){
			x = z->right;
			transplant(z, z->right);
		}else if(z->right == NIL){
			x = z->left;
			transplant(z, z->left);
		}else{
			y = minimum(z->right);
			y_originally_red = y->red;
			x = y->right;
			if(y->parent == z){
				x->parent = y;
			}else{
				transplant(y, y->right);
				y->right = z->right;
				y->right->parent = y;
			}
			transplant(z, y);
			y->left = z->left;
			y->left->parent = y;
			y->red = z->red;
		}
		if(y_originally_red == false){
			delete_fixup(x);
		}
	}

	void delete_fixup(node *x){
		while(x != root && x->red == false){
			if(x == x->parent->left){
				node *w = x->parent->right;
				if(w->red == true){
					w->red = false;
					x->parent->red = true;
					left_rotate(x->parent);
					w = x->parent->right;
				}
				if(w->left->red == false && w->right->red == false){
					w->red = true;
					x = x->parent;
				}else{
					if(w->right->red == false){
						w->left->red = false;
						w->red = true;
						right_rotate(w);
						w = x->parent->right;
					}
					w->red = x->parent->red;
					x->parent->red = false;
					w->right->red = false;
					left_rotate(x->parent);
					x = root;
				}
			}else{
				node *w = x->parent->left;
				if(w->red == true){
					w->red = false;
					x->parent->red = true;
					right_rotate(x->parent);
					w = x->parent->left;
				}
				if(w->right->red == false && w->left->red == false){
					w->red = true;
					x = x->parent;
				}else{
					if(w->left->red == false){
						w->right->red = false;
						w->red = true;
						left_rotate(w);
						w = x->parent->left;
					}
					w->red = x->parent->red;
					x->parent->red = false;
					w->left->red = false;
					right_rotate(x->parent);
					x = root;
				}
			}
		}
		x->red = false;
	}

	node *search(Int k){
		node *x = root;
		while(x != NIL){
			if(x->key == k) break;
			else if(x->key < k) x = x->right;
			else x = x->left;
		}
		return x;
	}

	node *minimum(node *x){
		while(x->left != NIL) x = x->left;
		return x;
	}

	node *maximum(node *x){
		while(x->right != NIL) x = x->right;
		return x;
	}

	node *successor(node *x){
		if(x->right != NIL) return minimum(x->right);
		node *y = x->parent;
		while(y != NIL && x == y->right){
			x = y;
			y = y->parent;
		}
		return y;
	}

	node *predecessor(node *x){
		if(x->left != NIL) return maximum(x->left);
		node *y = x->parent;
		while(y != NIL && x == y->left){
			x = y;
			y = y->parent;
		}
		return y;
	}

	void inorder_tree_walk(node *x, std::queue<Int> &q){
		if(x == NIL) return;
		inorder_tree_walk(x->left, q);
		q.push(x->key);
		inorder_tree_walk(x->right, q);
	}

	void preorder_tree_walk(node *x, std::queue<Int> &q){
		if(x == NIL) return;
		q.push(x->key);
		preorder_tree_walk(x->left, q);
		preorder_tree_walk(x->right, q);
	}
	
	void print(){
		std::cerr << "size = " << size << "\n";
		print(root, 0, 0);
	}

	void print(node *x, size_t dep, size_t lr){
		if(x == NIL) return;
		print(x->right, dep+1, 1);
		for(size_t i=0; i<dep; i++) std::cerr << "  ";
		if(!lr) std::cerr << "--";
		else if(lr == 1) std::cerr << "|‾";
		else std::cerr << "|_";
		if(x->red) std::cerr << "\x1b[31m";
		std::cerr << x->key << std::endl;
		std::cerr << "\x1b[0m";
		print(x->left, dep+1, 2);
	}
};

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	Int n; cin >> n;
	redblack_tree rbt;
	for(Int i=0; i<n; ++i){
		string s;
		cin >> s;
		if(s == "insert"){
			Int v;
			cin >> v;
			rbt.insert(v);
		}else{
			queue<Int> q;
			rbt.inorder_tree_walk(rbt.root, q);
			while(!q.empty()){
				cout << " " << q.front();
				q.pop();
				if(q.empty()) cout << "\n";
			}
			rbt.preorder_tree_walk(rbt.root, q);
			while(!q.empty()){
				cout << " " << q.front();
				q.pop();
				if(q.empty()) cout << "\n";
			}
		}
	}
}


Measured memory_bytes: 30296