#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <cassert>
#include <ctime>
#include <map>

template<class T>
class Tree{
private:
	struct Node{
		Node*parent, *left, *right;
		T value;
	   
		explicit Node(const T&value):
			parent(0), left(0), right(0), value(value){}
	};
				
	Node*root;
public:
	Tree():root(0){}

	bool is_empty()const{
		return !root;
	}

	// ------------------------------------------------------------------ //

private:
	static bool is_left_child(const Node*node){
		if(node->parent == 0)
			return false; // Die Wurzel ist kein Kind
		else
			return node->parent->left == node;
	}

	static bool is_right_child(const Node*node){
		if(node->parent == 0)
			return false; // Die Wurzel ist kein Kind
		else
			return node->parent->right == node;
	}

	Node**get_parent_ptr(Node*node){
		if(node->parent == 0)
			return &root;
		else if(is_left_child(node))
			return &node->parent->left;
		else
			return &node->parent->right;
	}

	static std::string format_label(const Node*node){
		if(node){
			std::ostringstream out;
			out<<node->value;
			return out.str();
		}else
			return "";
	}

	static unsigned get_height(const Node*node){
		if(!node)
			return 0;
		unsigned left_height = 0, right_height = 0;
	
		if(node->left)
			left_height = get_height(node->left);
		if(node->right)
			right_height = get_height(node->right);
	
		// Der höchste Unterbaum bestimmt die Gesamthöhe
		return std::max(left_height, right_height) + 1;
	}

	static unsigned get_width(const Node*node){
		if(!node)
			return 0;
		unsigned left_width = 0, right_width = 0;
	
		if(node->left)
			left_width = get_width(node->left);
		if(node->right)
			right_width = get_width(node->right);
	
		return left_width + format_label(node).length() + right_width;
	}

	static void dump_spaces(std::ostream&out, unsigned count){
		for(unsigned i=0; i<count; ++i)
			out.put(' ');
	}

	static void dump_line(std::ostream&out, const Node*node, unsigned line){
		if(!node)
			return;
		if(line == 1){
			// Die Wurzel des Unterbaums soll ausgegeben werden
			dump_spaces(out, get_width(node->left));
			out<<format_label(node);
			dump_spaces(out, get_width(node->right));
		}else{
			// In beiden Unterbäumen sind die Wurzeln um eins niedriger und darum verändert
			// sich die Zeilennummerierung.
			dump_line(out, node->left, line-1);
			dump_spaces(out, format_label(node).length());
			dump_line(out, node->right, line-1);
		}
	}

	static void dump_node(std::ostream&out, const Node*node){
		for(unsigned line=1, height = get_height(node); line <= height; ++line){
			dump_line(out, node, line);
			out.put('\n');
		}
		out.flush();
	}

public:
	void dump(std::ostream&out)const{
		dump_node(out, root);
	}

private:
	bool is_wellformed(Node*node){
		if(node == 0)
			return true;
		if(*get_parent_ptr(node) != node)
			return false;
		if(!is_wellformed(node->left))
			return false;
		if(!is_wellformed(node->right))
			return false;
		return true;
	}

	// ------------------------------------------------------------------ //

public:
	~Tree(){
		Node*now = root;
		while(now){   
			if(now->left)
				now = now->left;
			else if(now->right)
				now = now->right;
			else{
				Node*next = now->parent;
				*get_parent_ptr(now) = 0;
				delete now;
				now = next;
			}
		}
	}

	Tree(const Tree&other){
		if(other.is_empty())
			root = 0;
		else{
			root = new Node(other.root->value);
			try{
				Node
					*now = root,
					*other_now = other.root;
				while(other_now){
					if(other_now->left && !now->left){
						now->left = new Node(other_now->left->value);
						now->left->parent = now;
						now = now->left;
						other_now = other_now->left;
					}else if(other_now->right && !now->right){
						now->right = new Node(other_now->right->value);
						now->right->parent = now;
						now = now->right;
						other_now = other_now->right;
					}else{
						now = now->parent;
						other_now = other_now->parent;
					}
					assert(is_wellformed(root));
				}
			}catch(...){
				this->~Tree();
				throw;
			}
		}
	}

public:
	void swap(Tree&other){
		std::swap(root, other.root);
	}
	
	Tree&operator=(const Tree&other){
		Tree temp(other);
		swap(temp);
		return *this;
	}

	// ------------------------------------------------------------------ //

private:
	template<class NodeT>
	static NodeT*search(NodeT*root, const T&value){
		NodeT*now = root;
		while(now){
			if(value < now->value)
				now = now->left;
			else if(now->value < value)
				now = now->right;
			else
				return now;
		}
		return 0;
	}

public:
	bool contains(const T&t)const{
		return search(root, t);
	}
	
	// ------------------------------------------------------------------ //

public:
	bool insert(const T&value){
		Node
			*parent = 0,
			*now = root;
		bool is_left_child = false;
		while(now){
			parent = now;
			if(value < now->value){
				is_left_child = true;
				now = now->left;
			}else if(now->value < value){
				is_left_child = false;
				now = now->right;
			}else
				return false; // Das Element ist bereits im Baum
		}
		Node*new_node = new Node(value);
		new_node->parent = parent;
	   
		if(parent == 0)
			root = new_node;
		else if(is_left_child)
			parent->left = new_node;
		else
			parent->right = new_node;
	   
	   
		// Wenn etwas mit den Zeigern falsch ist,
		// dann knallt es wahrscheinlich hier.
		assert(is_wellformed(root));
		return true;
	}

	// ------------------------------------------------------------------ //

private:
	void swap_near_nodes(Node*child, Node*parent){
		// Als erstes passen wir den unbeteiligten Großelternknoten an.
		*get_parent_ptr(parent) = child;
	   
		// Anschließend werden die Kind- und Elternzeiger ausgetauscht.
		std::swap(parent->left, child->left);
		std::swap(parent->right, child->right);
		std::swap(parent->parent, child->parent);
	   
		// Da eines der Kinder getauscht wird, benötigt es eine
		// Sonderbehandlung.
		if(child->left == child)
			child->left = parent;
		else
			child->right = parent;
	   
		// Nun sind alle Kindzeiger richtig und die Elternzeiger können
		// dem angepasst werden.
		if(child->left)
			child->left->parent = child;
		if(child->right)
			child->right->parent = child;
		if(parent->left)
			parent->left->parent = parent;
		if(parent->right)
			parent->right->parent = parent;
		   
		// Na, wer ist sich noch sicher, ob wir nicht
		// bereits Zeigersalat haben? Besser testen!
		assert(is_wellformed(root));
	}
	
	void swap_far_nodes(Node*a, Node*b){
		// Zuerst updaten wir die Zeiger der Eltern
		*get_parent_ptr(a) = b;
		*get_parent_ptr(b) = a;
	
		// Danach der Kinder
		if(a->left)
			a->left->parent = b;
		if(a->right)
			a->right->parent = b;
		if(b->left)
			b->left->parent = a;
		if(b->right)
			b->right->parent = a;
	
		// Und als letztes die der beiden Knoten
		std::swap(a->left, b->left);
		std::swap(a->right, b->right);
		std::swap(a->parent, b->parent);
	
		assert(is_wellformed(root));
	}
	
	void swap_nodes(Node*a, Node*b){
		if(a->parent == b)
			swap_near_nodes(a, b);
		else if(b->parent == a)
			swap_near_nodes(b, a);
		else
			swap_far_nodes(a, b);
	}

	// ------------------------------------------------------------------ //

private:
	template<class NodeT>
	static NodeT*get_min(NodeT*node){
		NodeT*now = node;
		while(now->left)
			now = now->left;
		return now;
	}
	
	template<class NodeT>
	static NodeT*get_max(NodeT*node){
		NodeT*now = node;
		while(now->right)
			now = now->right;
		return now;
	}
	
	
public:
	const T&min()const{
		return get_min(root)->value;
	}
	
	const T&max()const{
		return get_max(root)->value;
	}
	
	// ------------------------------------------------------------------ //

private:
	template<class NodeT>
	static NodeT*get_next_node(NodeT*now){
		if(now->right)
			return get_min(now->right);
		else{
			while(now){
				if(is_left_child(now))
					return now->parent;
				else
					now = now->parent;
			}
			return 0; // Wir sind am Ende angekommen
		}
	}
	
	template<class NodeT>
	static NodeT*get_prev_node(NodeT*now){
		if(now->left)
			return get_max(now->left);
		else{
			while(now){
				if(is_right_child(now))
					return now->parent;
				else
					now = now->parent;
			}
			return 0; // Wir sind am Anfang angekommen
		}
	}
	
public:
	const T*next(const T&value)const{
		const Node*now = search(root, value);
		if(!now)
			return 0;
		now = get_next_node(now);
		if(now)
			return &now->value;
		else
			return 0;
	}
	
	const T*prev(const T&value)const{
		const Node*now = search(root, value);
		if(!now)
			return 0;
		now = get_prev_node(now);
		if(now)
			return &now->value;
		else
			return 0;
	}

	// ------------------------------------------------------------------ //

private:
	void remove(Node*node){
		// Ein Blatt
		if(!node->left && !node->right){
			*get_parent_ptr(node) = 0;
			delete node;
		}
		// Nur ein Kind
		else if(node->left && !node->right){
			*get_parent_ptr(node) = node->left;
			node->left->parent = node->parent;
			delete node;
		}else if(!node->left && node->right){
			*get_parent_ptr(node) = node->right;
			node->right->parent = node->parent;
			delete node;
		}
		// Zwei Kinder
		else{
			Node*other = get_prev_node(node);
			swap_nodes(node, other);
			// Löschen des Knotens durch Benutzen von einer
			// der beiden anderen Methoden
			remove(node);
		}
		assert(is_wellformed(root));
	}
public:
	bool remove(const T&value){
		Node*node = search(root, value);
		if(node){
			remove(node);
			return true;
		}else
			return false;
	}

	// ------------------------------------------------------------------ //
	
private:
	Node*rotate_left(Node*A){
		Node
			**root_ptr = get_parent_ptr(A),
			*parent = A->parent,
			*B = A->right,
			*X = A->left,
			*Y = B->left,
			*Z = B->right;
		   
		*root_ptr = B;
		B->left = A;
		B->right = Z;
		A->left = X;
		A->right = Y;
		   
		B->parent = parent;
		A->parent = B;
		if(Z)
			Z->parent = B;
		if(X)
			X->parent = A;
		if(Y)
			Y->parent = A;
		   
		return B;
	}

	Node*rotate_right(Node*A){
		Node
			**root_ptr = get_parent_ptr(A),
			*parent = A->parent,
			*B = A->left,
			*X = B->left,
			*Y = B->right,
			*Z = A->right;
	   
		*root_ptr = B;
		B->left = X;
		B->right = A;
		A->left = Y;
		A->right = Z;
	   
		B->parent = parent;
		A->parent = B;
		if(Z)
			Z->parent = A;
		if(X)
			X->parent = B;
		if(Y)
			Y->parent = A;
		   
		return B;
	}
	
	//
	// Folgende Funktionen werden nicht im Artikel behandelt und haben an sich auch nichts
	// im public-Interface eines normalen Baums zu suchen. Der einzige Grund wieso sie
	// dennoch hier sind, ist um die Rotationen testen zu können.
	//
public:
	bool rotate_left(const T&value){
		Node*node = search(root, value);
		if(node && node->right){
			rotate_left(node);
			return true;
		}else
			return false;
	}
	
	bool rotate_right(const T&value){
		Node*node = search(root, value);
		if(node && node->left){
			rotate_right(node);
			return true;
		}else
			return false;
	}
};

// ------------------------------------------------------------------ //
//	Experimentierkonsole
// ------------------------------------------------------------------ //

using namespace std;

namespace cmd{
	typedef void (*ptr)(Tree<int>&t, istream&in, ostream&out);

	void help(Tree<int>&t, istream&in, ostream&out){
		out
			<<"List of commands : \n"
		
			<<"\t\thelp\n"
			<<"\tPrints this message.\n\n"
		
			<<"\t\texit\n"
			<<"\tEnds the program.\n\n"
		
			<<"\t\tcontains n\n"
			<<"\tTests if n is in the tree.\n\n"
		
			<<"\t\tmin\n"
			<<"\tPrints the minimal value.\n\n"
		
			<<"\t\tmax\n"
			<<"\tPrints the maximal value.\n\n"
		
			<<"\t\tnext n\n"
			<<"\tPrints the element before n.\n\n"
		
			<<"\t\tprev n\n"
			<<"\tPrints the element after n.\n\n"
		
			<<"\t\tadd n1 [n2 [...]]\n"
			<<"\tInserts a number of values into the tree.\n\n"
		
			<<"\t\trandom_add max_count min max\n"
			<<"\tAdd at most max_count random values in the range [min, max] into the tree.\n\n"
		
			<<"\t\tremove n1 [n2 [...]]\n"
			<<"\tRemoves a number of values from the tree.\n\n"
		
			<<"\t\trandom_remove max_count\n"
			<<"\tRemoves at most max_count random values from the tree.\n\n"
		
			<<"\t\tclear\n"
			<<"\tRemoves each value from the tree.\n\n"
			
			<<"\t\trotate_left n\n"
			<<"\tDoes a left rotation around n.\n\n"
			
			<<"\t\trotate_right n\n"
			<<"\tDoes a right rotation around n.\n\n"
			
			<<"\t\tsave\n"
			<<"\tBacks up the current tree.\n\n"
			
			<<"\t\tload\n"
			<<"\tLoads the tree stored by the last save command.\n\n"
			
			<<"\t\tview_save\n"
			<<"\tPrints the last tree stored by the last save command.\n\n"
		;
	}
	
	void contains(Tree<int>&t, istream&in, ostream&out){
		int value;
		if(in>>value){
			out<<value<<" is ";
			if(!t.contains(value))
				out<<"not ";
			out<<"in the tree.";
		}else
			out<<"Error : Could not parse the value";
	}
	
	void min(Tree<int>&t, istream&in, ostream&out){
		if(t.is_empty())
			out<<"Error : The tree is empty.";
		else
			out<<"The minimum is "<<t.min();
	}
	
	void max(Tree<int>&t, istream&in, ostream&out){
		if(t.is_empty())
			out<<"Error : The tree is empty.";
		else
			out<<"The maximum is "<<t.max();
	}
	
	void next(Tree<int>&t, istream&in, ostream&out){
		int value;
		if(in>>value){
			const int*other = t.next(value);
			if(other)
				out<<"The value after "<<value<<" is "<<*other<<'.';
			else
				out<<"Error : "<<value<<" is the last element.";
		}else
			out<<"Error : Could not parse the value";
	}
	
	void prev(Tree<int>&t, istream&in, ostream&out){
		int value;
		if(in>>value){
			const int*other = t.prev(value);
			if(other)
				out<<"The value before "<<value<<" is "<<*other<<'.';
			else
				out<<"Error : "<<value<<" is the first element.";
		}else
			out<<"Error : Could not parse the value";
	}
	
	void add(Tree<int>&t, istream&in, ostream&out){
		int value;
		while(in>>value){
			if(!t.insert(value))
				out<<"Error : "<<value<<" is already in the tree.\n";
		}
		if(!in.eof())
			out<<"Error : Could not parse a value";
	}
	
	void random_add(Tree<int>&t, istream&in, ostream&out){
		unsigned max_count;
		int min, max;
	
		if(in>>max_count>>min>>max){
			out<<"Adding at most "<<max_count<<" elements";
			for(unsigned i=0; i<max_count; ++i)
				t.insert(rand()%(max - min + 1) + min);
		}else
			out<<"Could not parse parameters.";
	}
	
	void remove(Tree<int>&t, istream&in, ostream&out){
		int value;
		while(in>>value){
			if(!t.remove(value))
				out<<"Error : "<<value<<" was not in the tree.\n";
		}
		if(!in.eof())
			out<<"Error : Could not parse a value";
	}
	
	void random_remove(Tree<int>&t, istream&in, ostream&out){
		unsigned max_count;
		
		if(in>>max_count){
			const int*ptr;
			out<<"Removing at most "<<max_count<<" random elements : ";
			for(int i=t.min(); (ptr = t.next(i)) && max_count; i = *ptr){
				if(rand()%5 == 0){
					out<<i<<' ';
					assert(t.remove(i));
					--max_count;
				}
			}
		}else
			out<<"Could not parse parameters";
	}
	
	void rotate_left(Tree<int>&t, istream&in, ostream&out){
		int value;
		if(in>>value){
			if(t.rotate_left(value))
				out<<"Tree rotated left around "<<value<<'.';
			else
				out<<"Could not rotate left around "<<value<<'.';
		}else
			out<<"Error : Could not parse the value";
	}
	
	void rotate_right(Tree<int>&t, istream&in, ostream&out){
		int value;
		if(in>>value){
			if(t.rotate_right(value))
				out<<"Tree rotated left around "<<value<<'.';
			else
				out<<"Could not rotate left around "<<value<<'.';
		}else
			out<<"Error : Could not parse the value";
	}
	
	void clear(Tree<int>&t, istream&in, ostream&out){
		Tree<int>temp;
		temp.swap(t);
		out<<"Tree cleared";
	}
	
	Tree<int>saved_tree;
	
	void save(Tree<int>&t, istream&in, ostream&out){
		saved_tree = t;
		out<<"Tree saved";
	}
	
	void load(Tree<int>&t, istream&in, ostream&out){
		t = saved_tree;
		out<<"Tree loaded";
	}
	
	void view_save(Tree<int>&t, istream&in, ostream&out){
		out<<"The following is the saved tree : "<<endl;
		saved_tree.dump(out);
	}
}

void print_head(const Tree<int>&t, ostream&out){
	if(t.is_empty())
		out<<"The tree is empty."<<endl;
	else
		t.dump(out);
	
	out<<"\n > ";
}

void print_tail(const Tree<int>&t, ostream&out){
	out<<"\n=================================================================\n"<<endl;
}

void run_terminal(const map<string, cmd::ptr>&cmd_map, istream&in, ostream&out){
	Tree<int>t;
	
	string line;
	
	print_head(t, out);
	while(getline(in, line)){
		istringstream cmd_in(line);
		string cmd_name;
		cmd_in>>cmd_name;
		out<<'\n';
		
		if(cmd_name == "exit")
			break;
		
		map<string, cmd::ptr>::const_iterator found = cmd_map.find(cmd_name);
		if(found != cmd_map.end()){
			(*found->second)(t, cmd_in, out);
			
			char c;
			if(cmd_in>>c)
				out<<"Error : additional parameters ignored"<<endl;
				
			out<<std::endl;
		}else
			out<<"Error : unknown command \""<<cmd_name<<"\". Type \"help\" for a list of commands."<<endl;
		
		print_tail(t, out);
		print_head(t, out);
	}
}

int main(){
	try{
		srand(time(0));
	
		map<string, cmd::ptr>cmd_map;
		
		cmd_map["?"] = &cmd::help;
		cmd_map["help"] = &cmd::help;
		cmd_map["add"] = &cmd::add;
		cmd_map["contains"] = &cmd::contains;
		cmd_map["remove"] = &cmd::remove;
		cmd_map["min"] = &cmd::min;
		cmd_map["max"] = &cmd::max;
		cmd_map["random_add"] = &cmd::random_add;
		cmd_map["random_remove"] = &cmd::random_remove;
		cmd_map["next"] = &cmd::next;
		cmd_map["prev"] = &cmd::prev;
		cmd_map["rotate_left"] = &cmd::rotate_left;
		cmd_map["rotate_right"] = &cmd::rotate_right;
		cmd_map["clear"] = &cmd::clear;
		cmd_map["save"] = &cmd::save;
		cmd_map["load"] = &cmd::load;
		cmd_map["view_save"] = &cmd::view_save;
		
		run_terminal(cmd_map, cin, cout);
	}catch(std::exception&error){
		cerr<<"Fatal error : Stopped on exception throw : "<<error.what();
	}catch(...){
		cerr<<"Fatal error : Stopped on unknown exception throw.";
	}
}