#include <string>
#include <iostream>
#include <cstdlib>

using namespace std;

int DEBUG = 0;

class AVL_Tree{
	private :
		enum visited{no,yes};
		typedef struct NODE{
			int  data;
			NODE *left_child;
			NODE *right_child;
			NODE *parent;
			int height_at_left;
			int height_at_right;
			int visited;
		}node;
		node *root;
		bool tree_deleted;

	private:
		void * balance_the_tree (node *);
		void * right_rotation (node *child);
		void * left_rotation (node *child);
		void update_tree_height (node *);
		void update_parent (node *, node *);
		void print_node (node *);
		void print_or_delete (int);
		void reset_tree (void);
	public :
		AVL_Tree ();
		AVL_Tree (int);
		void add_node (int);
		void * search_tree (int);
		void print_tree ();
		void delete_tree ();
		void delete_node (int);
		~AVL_Tree();
};

AVL_Tree::AVL_Tree (){
	root = new (node);
	root->data = 0;
	root->parent = NULL;
	root->left_child = NULL;
	root->right_child = NULL;
	root->height_at_left = 0;
	root->height_at_right = 0;
	tree_deleted = false;
};


AVL_Tree::AVL_Tree (int data){
	root = new (node);
	root->data = data;
	root->parent = NULL;
	root->left_child = NULL;
	root->right_child = NULL;
	root->height_at_left = 0;
	root->height_at_right = 0;
	tree_deleted = false;
};

void AVL_Tree::add_node (int data){
    if (search_tree (data)!=NULL) return;
	bool ldone = false;
	if (DEBUG)
		cout << "\t@AVL_Tree::add_node node to be added: " << data << ".\n";
	while (!ldone){
		if (data == root->data){
			if (DEBUG)
				cout << "\t@AVL_Tree::add_node duplicate: " << data
				<<" root:" << root->data << ".\n";
			ldone = true;
		}
		else
		if(root->data == 0){
				if (sizeof(root->left_child) >= sizeof(node))
					delete(root->left_child);
				if (sizeof(root->right_child) >= sizeof(node))
					delete(root->right_child);
				root->data = data;
				root->left_child = NULL;
                root->right_child = NULL;
				root->height_at_left = 0;
				root->height_at_right = 0;
				root->visited = no;
				ldone = true;
				continue;
		}else
		if(data > root->data){
			root->height_at_right++;
			if (root->right_child == NULL){
				node *temp = new (node);
				temp->parent = root;
				temp->data = data;
				temp->left_child = NULL;
                temp->right_child = NULL;
				temp->height_at_left = 0;
				temp->height_at_right = 0;
				temp->visited = no;
				root->right_child = temp;
				ldone = true;
				continue;
			}else
				root = root->right_child;
			if (DEBUG)
				cout << "@AVL_Tree::add_node adding to right of node:" << root->parent->data
				<< " right_height: " << root->parent->height_at_right <<".\n";

			continue;
		}else
		if(data < root->data){
			root->height_at_left++;
			if (root->left_child == NULL){
				node *temp = new (node);
				temp->parent = root;
				temp->data = data;
				temp->left_child = NULL;
                temp->right_child = NULL;
				temp->height_at_left = 0;
				temp->height_at_right = 0;
				temp->visited = no;
				root->left_child = temp;
				ldone = true;
				continue;
			}else
				root = root->left_child;
			if (DEBUG)
				cout << "@AVL_Tree::add_node adding to left of node:" << root->parent->data
				<< " left_height: " << root->parent->height_at_left <<".\n";
			continue;
		}
	}
	root = (node *) balance_the_tree (root);
	return;
};

void * AVL_Tree::balance_the_tree (node *child){
	if (DEBUG)
		cout << "@AVL_Tree::balance_the_tree called @ node: " << child->data <<".\n";
	bool ldone = false;
    int lright_rotation = 0, lleft_rotation = 0;
	while (!ldone){
		if(child->height_at_left - child->height_at_right < 2 &&
						child->height_at_right - child->height_at_left < 2){
			if (DEBUG){
				cout << "@AVL_Tree::balance_the_tree no rotation needed @ ";
				print_node (child);
			}
			if (child->parent == NULL){
				ldone = true;
				if (DEBUG)
				cout <<"\n";
				continue;
			}else{
					if (child->parent != NULL && child == child->parent->left_child)
						child->parent->height_at_left =
								child->height_at_right > child->height_at_left?
								child->height_at_right+1:child->height_at_left+1;
					else
					if (child->parent != NULL && child == child->parent->right_child)
						child->parent->height_at_right =
								child->height_at_right > child->height_at_left?
								child->height_at_right+1:child->height_at_left+1;
					child = child->parent;
			}
			if (DEBUG)
				cout <<"\n";
		}else
		if (child->height_at_left - child->height_at_right > 1){
			if (lright_rotation == 1){
				if (DEBUG)
					cout << "@AVL_Tree::balance_the_tree left_right_rotation "
					<< " needed @ node: " << child->data
					<< " left height: "<< child->height_at_left
					<< " right height: "<< child->height_at_right<<".\n";
 				child = (node *)left_rotation (child->left_child);
 					update_tree_height (child);
                if (child->height_at_left - child->height_at_right >= 2 && child->parent!=NULL)
                    child = (node *)right_rotation (child->parent);
                lright_rotation = 0;
				continue;
			}
			child = (node *)right_rotation (child);
			lright_rotation++;
		}else
		if (child->height_at_right - child->height_at_left > 1){
			if (lleft_rotation == 1){
				if (DEBUG)
					cout << "@AVL_Tree::balance_the_tree right_left_rotation"
					<< " needed @ node: " << child->data
					<< " left height: "<< child->height_at_left
					<< " right height: "<< child->height_at_right<<".\n";
				child = (node *)right_rotation (child->right_child);
				update_tree_height (child);
				if (child->height_at_right - child->height_at_left >= 2 && child->parent!=NULL)
                    child = (node *)left_rotation (child->parent);
                lleft_rotation = 0;
				continue;
			}
			child = (node *)left_rotation (child);
            lleft_rotation++;
		}
	}
	return child;
}

void * AVL_Tree::right_rotation (node *child){
	if (DEBUG){
		cout << "@AVL_Tree::right_rotation before rotation @ node: ";
		print_node (child);
	}
	node *temp = child->left_child;
	child->left_child = temp->right_child;
	if (temp->right_child != NULL)
		temp->right_child->parent = child;
	temp->right_child = child;
	child->height_at_left = temp->height_at_right;
	temp->height_at_right =
			child->height_at_right > child->height_at_left?
			child->height_at_right+1:child->height_at_left+1;
	update_parent (child, temp);
	update_tree_height (child);
	temp->parent = child->parent;
	child->parent = temp;
	child = temp;
	if (DEBUG){
		cout << "@AVL_Tree::right_rotation after rotation node: ";
		print_node (child);
	}
	return child;
}

void * AVL_Tree::left_rotation (node *child){
	if (DEBUG){
		cout << "@AVL_Tree::left_rotation before rotation @ node: ";
		print_node (child);
	}
	node *temp = child->right_child;
	child->right_child = temp->left_child;
	if (temp->left_child != NULL)
		temp->left_child->parent = child;
	temp->left_child = child;
	child->height_at_right = temp->height_at_left;
	temp->height_at_left =
			child->height_at_left > child->height_at_right?
			child->height_at_left+1:child->height_at_right+1;
	update_parent (child, temp);
	update_tree_height (child);
	temp->parent = child->parent;
	child->parent = temp;
	child = temp;
	if (DEBUG){
		cout << "@AVL_Tree::left_rotation after rotation node: ";
		print_node (child);
	}
	return child;
}

void AVL_Tree::print_node (node * child){
	if (child == root)	cout << "root: ";
	else cout << "node: " ;
	cout<< child->data;
	if (child->left_child != NULL)
		cout <<" left_child: " << child->left_child->data;
	if (child->right_child != NULL)
		cout <<" right_child: " << child->right_child->data;
	cout <<" left_height: " << child->height_at_left;
	cout <<" right_height: " << child->height_at_right;
	if (child->parent != NULL)
		cout << " parent: " << child->parent->data;
	cout << ".\n";
	return;
}

void AVL_Tree:: update_tree_height (node *child){
	while (child!= NULL){
		if (DEBUG){
			cout << "@AVL_Tree:update_tree_height called @ node: " << child->data << ".\n";
			print_node (child);
		}
		if (child->parent!= NULL && child == child->parent->left_child)
			child->parent->height_at_left =
					child->height_at_left > child->height_at_right?
					child->height_at_left+1:child->height_at_right+1;

		else
		if (child->parent!= NULL && child == child->parent->right_child)
			child->parent->height_at_right =
					child->height_at_left > child->height_at_right?
					child->height_at_left+1:child->height_at_right+1;

		child = child->parent;
	}
	return;
}

void AVL_Tree:: update_parent (node *child, node *temp){
	if (child->parent!= NULL && child == child->parent->left_child)
			child->parent->left_child = temp;
	else
	if (child->parent!= NULL && child == child->parent->right_child)
			child->parent->right_child = temp;
	return;
}

void * AVL_Tree::search_tree (int data){
	node *lroot = root, *lparent = NULL;
	if (root == NULL) return NULL;
	bool ldone = false;
	while (!ldone){
                if (lroot == NULL) ldone = true;
                else
		if(lroot->data == data) ldone = true;
		else
		if(data > lroot->data){
			lparent = lroot;
			lroot = lroot->right_child;
		}else
		if(data < lroot->data){
			lparent = lroot;
			lroot = lroot->left_child;
                }
	}
	return lroot;
}

void AVL_Tree::reset_tree (void){
	node *lroot = root;
	bool ldone = false;
	while (!ldone){
		if (lroot == NULL)ldone= true;
		else
		if (lroot->left_child != NULL && lroot->left_child->visited == yes)
			lroot = lroot->left_child;
		else
		if (lroot->visited == yes){
			lroot->visited = no;
		}
		else
		if (lroot->right_child != NULL && lroot->right_child->visited == yes)
			lroot = lroot->right_child;
		else
			lroot = lroot->parent;
	}
	return;
}

void AVL_Tree::print_or_delete (int erase){
	node *lroot = root;
	bool ldone = false;
	while (!ldone){
		if (lroot == NULL)ldone= true;
		else
		if (lroot->left_child != NULL && lroot->left_child->visited == erase)
			lroot = lroot->left_child;
		else
		if (lroot->visited == erase){
			if(!erase){
				if (lroot->left_child != NULL && lroot->right_child != NULL) print_node (lroot);
			}else
				lroot->data = 0;
			lroot->visited = !erase;
		}
		else
		if (lroot->right_child != NULL && lroot->right_child->visited == erase)
			lroot = lroot->right_child;
		else
			lroot = lroot->parent;
	}
	return;
}

void AVL_Tree::delete_tree (){
	print_or_delete(1);
	tree_deleted  = true;
	return;
}

void AVL_Tree::print_tree (){
	if (DEBUG)
		cout << "\t@AVL_Tree:print_tree root " << root->data << "\n";
	if (tree_deleted == false) {
		reset_tree ();
		print_or_delete(0);
	}
	else
	if (DEBUG)
		cout << "The Tree has been deleted.\n";
	return;
}

void AVL_Tree::delete_node (int data){
	if (DEBUG)
		cout << "\t@AVL_Tree:delete_node called for Node " << data << ".\n";
	bool ldone = false;
	node *to_be_deleted = (node *) search_tree (data);
	if (to_be_deleted == NULL){
		cout << "Node " << data << " not found.\n";
		return;
	}
	while (!ldone){
		if (to_be_deleted->right_child != NULL &&
				to_be_deleted->right_child->left_child != NULL){
			to_be_deleted->data = to_be_deleted->right_child->left_child->data;
			to_be_deleted = to_be_deleted->right_child->left_child;
		}else
		if (to_be_deleted->left_child != NULL &&
				to_be_deleted->left_child->right_child != NULL){
			to_be_deleted->data = to_be_deleted->left_child->right_child->data;
			to_be_deleted = to_be_deleted->left_child->right_child;
		}else
		if (to_be_deleted->right_child != NULL){
			to_be_deleted->data = to_be_deleted->right_child->data;
			to_be_deleted = to_be_deleted->right_child;
		}else
		if (to_be_deleted->left_child != NULL){
			to_be_deleted->data = to_be_deleted->left_child->data;
			to_be_deleted = to_be_deleted->left_child;
		}else{
			if (to_be_deleted == to_be_deleted->parent->left_child){
				to_be_deleted->parent->height_at_left = 0;
				to_be_deleted->parent->left_child = NULL;
			}
			else{
				to_be_deleted->parent->height_at_right = 0;
				to_be_deleted->parent->right_child = NULL;
			}
			update_tree_height (to_be_deleted->parent);
			balance_the_tree (to_be_deleted->parent);
			delete (to_be_deleted);
			ldone = true;
		}
	}
	if (DEBUG)
		cout << "\t@AVL_Tree:delete_node node " << data << " deleted.\n";
	return;
}


AVL_Tree::~AVL_Tree (){
	if (DEBUG)
		cout << "\n@AVL_Tree::~Tree Destructor called.\n";
	node *lroot = root, *temp = NULL;
	bool ldone = false;
	while (!ldone){
		if (lroot == NULL)ldone = true;
		else
		if (lroot->left_child != NULL)
			lroot = lroot->left_child;
		else
		if (lroot->right_child != NULL)
			lroot = lroot->right_child;
		else
		if (lroot->left_child == NULL && lroot->right_child == NULL){
			if (DEBUG)
				cout << "@AVL_Tree::~Tree node: " << lroot->data;
			if (lroot->parent != NULL && lroot == lroot->parent->left_child){
				temp = lroot->parent->left_child;
				lroot->parent->left_child = NULL;
			}
			else
			if (lroot->parent != NULL && lroot == lroot->parent->right_child){
				temp = lroot->parent->right_child;
				lroot->parent->right_child = NULL;
			}

			if (temp != NULL){
				delete (temp);
				temp = NULL;
				lroot = lroot->parent;
				if (DEBUG)
                    if (lroot!=NULL)
					cout << "@AVL_Tree::~Tree parent: " << lroot->data << ".\n";
			}
			else{
					if (DEBUG)
						cout << "@AVL_Tree::~Tree root: " << lroot->data << ".\n";
					delete (lroot);
					lroot = NULL;
			}
		}
	}
	if (DEBUG)
		cout << "\n@AVL_Tree::~TreeDestructor completed.\n";
	return;
};

int validate_input (string input){
		int lpos = 0, lsize = input.size();
		const char* lc = input.c_str();
		while (lpos < lsize)
		if (isdigit (*lc)){
			lpos++;
			lc++;
		}else
			return 1;
		return 0;
}


int main (void){
	AVL_Tree t;
	string lcmd = "";
	int lcount = 0, ldata = 0, lpos = 0, ln = 1;
	bool ldone = false, lvalidation = false;
	while (!ldone){
		if(lvalidation){
			lvalidation = false;
		}
		cin >> lcmd;
		if (isalpha(lcmd[0])){
			ldone = true;
			continue;
		}
		if (validate_input (lcmd)){
			cout << "Only numeric values allowed .\n";
			lcmd = "";
			lvalidation = true;
			continue;
		}
		lpos = lcmd.find(' ' );
		lcount = atoi(lcmd.substr(0, lpos).c_str());
		while (lcount > 0){

				cin >> lcmd;
				if (validate_input (lcmd)){
					cout << "Only numeric values allowed .\n";
					continue;
				}
				ldata = atoi(lcmd.substr(lpos+1,lcmd.find(' ' )).c_str());
				if (DEBUG )
				{
                    cout << "\n\t=================\t\n";
				    cout << ln++ << ": " <<ldata << endl;
				}
				t.add_node(ldata);
				if (DEBUG )
				{
                    t.print_tree ();
                    cout << "\n\t=================\t\n";
                }
				lcount--;
		}
        cout <<"\n";
		t.print_tree ();
		cout <<"\n";
		lcount = 0, ldata = 0;
	}
	return 0;
}
//Sample Inputs
//10 1 2 3 4 5 6 7 8 9 10
//10 10 9 8 7 6 5 4 3 2 1
//10 9 4 5 6 2 1 10 3 8 7
//10 3 1 2 9 4 5 8 7 10 6
//10 3 1 2 9 4 5 10 6 8 7