#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COMMAND_NUM 2000000000

#define SEARCH_TREE_RUN  1
#define SEARCH_TREE_STOP 0

#define ROOT_POINT       0
#define RIGHT_POINT      1
#define LEFT_POINT       2

typedef struct ST_TREE_POINT TreePoint_t;

struct ST_TREE_POINT{
	int key;				/* key value */
	TreePoint_t *top;		/* Top   Point */
	TreePoint_t *left;		/* Left  Point */
	TreePoint_t *right;		/* Right Point */
}TREE;

static void InsertPorocess(TreePoint_t **ptTreePoint, int key);
static int  InsertLeftProcess(TreePoint_t **ptTreePoint, int key);
static int  InsertRightProcess(TreePoint_t **ptTreePoint, int key);
static void SetTreePoint(TreePoint_t **ptTreePoint, int key, int direct);
static void InsertTreePoint(TreePoint_t **ptTreePoint, int key, int direct);
static void ExtractPorocess(TreePoint_t **ptTreePoint);
static void ExchangeTreePoint(TreePoint_t **ptTreePoint, int direct);
static void AllFreeProcess(TreePoint_t **ptTreePoint);

int main(void)
{
	int key;							/* insert key */
	char command[8];					/* command name */
	TreePoint_t *ptTreeTemp;			/* Tree Temp Data */
	TreePoint_t *ptRootPoint;			/* Tree Root Point */
	int loop = 0;
	
	/* Init Root Tree */
	ptRootPoint = NULL;
	
	/* get Name & time */
	while(((scanf("%s %d", command, &key)) != EOF) && loop <= MAX_COMMAND_NUM)
	{
		/* set Root point */
		if(ptRootPoint != NULL)
		{
			while( ptRootPoint->top != NULL )
			{
				ptRootPoint = ptRootPoint->top;
			}
			
			printf("root key = %d\n", ptRootPoint->key);
		}
		
		if( strncmp(command, "end", 3) == 0 ) /* End Process */
		{
			break;
		}
		else if( strncmp(command, "insert", 6) == 0 ) /* Insert Process */
		{
			InsertPorocess( &ptRootPoint, key );
		}
		else if( strncmp(command, "extract", 7) == 0 ) /* Extract Process */
		{
			ExtractPorocess( &ptRootPoint );
		}
		else
		{
			/* error input */
		}
		loop++;
	}
	
	/* all free process */
	AllFreeProcess(&ptRootPoint);
	
    return 0;
}

static void InsertPorocess(TreePoint_t **ptTreePoint, int key)
{
	int search_running_flag = SEARCH_TREE_RUN;
	
	if(*ptTreePoint == NULL)
	{
		SetTreePoint(ptTreePoint, key, ROOT_POINT);
	}
	else
	{
		while(search_running_flag == SEARCH_TREE_RUN)
		{
			if((*ptTreePoint)->key > key)
			{
				search_running_flag = InsertLeftProcess(ptTreePoint, key);
			}
			else
			{
				search_running_flag = InsertRightProcess(ptTreePoint, key);
			}
		}
	}
	
}

static int InsertLeftProcess(TreePoint_t **ptTreePoint, int key)
{
	TreePoint_t * ptTempTree;
	int ret;
	
	if((*ptTreePoint)->left == NULL)
	{
		SetTreePoint(ptTreePoint, key, LEFT_POINT);
		ret = SEARCH_TREE_STOP;
	}
	else
	{
		if((*ptTreePoint)->right == NULL)
		{
			ptTempTree = (*ptTreePoint)->left;
			if(ptTempTree->key <= key)
			{
				InsertTreePoint(ptTreePoint, key, LEFT_POINT);
				ret = SEARCH_TREE_STOP;
			}
			else
			{
				ExchangeTreePoint(ptTreePoint, LEFT_POINT);
				if((*ptTreePoint)->left == NULL)
				{
					SetTreePoint(ptTreePoint, key, LEFT_POINT);
					ret = SEARCH_TREE_STOP;
				}
				else
				{
					(*ptTreePoint) = (*ptTreePoint)->left;
					ret = SEARCH_TREE_RUN;
				}
			}
		}
		else
		{
			(*ptTreePoint) = (*ptTreePoint)->left;
			ret = SEARCH_TREE_RUN;
		}
	}
	
	return ret;
}

static int InsertRightProcess(TreePoint_t **ptTreePoint, int key)
{
	TreePoint_t * ptTempTree;
	int ret;
	
	if((*ptTreePoint)->right == NULL)
	{
		SetTreePoint(ptTreePoint, key, RIGHT_POINT);
		ret = SEARCH_TREE_STOP;
	}
	else
	{
		if((*ptTreePoint)->left == NULL)
		{
			ptTempTree = (*ptTreePoint)->right;
			
			if(ptTempTree->key > key)
			{
				InsertTreePoint(ptTreePoint, key, RIGHT_POINT);
				ret = SEARCH_TREE_STOP;
			}
			else
			{
				ExchangeTreePoint(ptTreePoint, RIGHT_POINT);
				if((*ptTreePoint)->right == NULL)
				{
					SetTreePoint(ptTreePoint, key, RIGHT_POINT);
					ret = SEARCH_TREE_STOP;
				}
				else
				{
					(*ptTreePoint) = (*ptTreePoint)->right;
					ret = SEARCH_TREE_RUN;
				}
			}
		}
		else
		{
			(*ptTreePoint) = (*ptTreePoint)->right;
			ret = SEARCH_TREE_RUN;
		}
	}
	
	return ret;
}
static void SetTreePoint(TreePoint_t **ptTreePoint, int key, int direct)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
	ptInsertData->key     = key;
	ptInsertData->top     = *ptTreePoint;
	ptInsertData->left    = NULL;
	ptInsertData->right   = NULL;

	if(direct == RIGHT_POINT)
	{
		(*ptTreePoint)->right = ptInsertData;
	}
	else if(direct == LEFT_POINT)
	{
		(*ptTreePoint)->left = ptInsertData;
	}
	else
	{
		(*ptTreePoint) = ptInsertData;
	}
}

static void InsertTreePoint(TreePoint_t **ptTreePoint, int key, int direct)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	TreePoint_t * ptOldTopTree;
	
	ptOldTopTree = (*ptTreePoint);
	
	ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
	ptInsertData->key     = key;
	ptInsertData->top     = ptOldTopTree->top;

	if(direct == RIGHT_POINT)
	{
		ptInsertData->left    = ptOldTopTree;
		ptInsertData->right   = ptOldTopTree->right;
		
		/* change Tree Old Top */
		ptOldTopTree = ptInsertData->right; /* need change point by segmentation */
		ptOldTopTree->top = ptInsertData;
		ptOldTopTree->left = NULL;
	}
	else
	{
		ptInsertData->left    = ptOldTopTree->left;
		ptInsertData->right   = ptOldTopTree;
		
		/* change Tree Old Top */
		ptOldTopTree = ptInsertData->left; /* need change point by segmentation */
		ptOldTopTree->top = ptInsertData;
		ptOldTopTree->right = NULL;
	}
	
	(*ptTreePoint) = ptInsertData;
	if((*ptTreePoint)->top != NULL)
	{
		(*ptTreePoint) = (*ptTreePoint)->top;
		if((*ptTreePoint)->key > key)
		{
			(*ptTreePoint)->left = ptInsertData;
		}
		else
		{
			(*ptTreePoint)->right = ptInsertData;
		}
	}
	
}

static void ExtractPorocess(TreePoint_t **ptTreePoint)
{
	TreePoint_t * ptTempTree;
	
	if((*ptTreePoint) != NULL)
	{
		/* serch max key */
		while((*ptTreePoint)->right != NULL)
		{
			(*ptTreePoint) = (*ptTreePoint)->right;
		}
		
		printf("%d\n", (*ptTreePoint)->key);
		
		if((*ptTreePoint)->left != NULL)		/* delete point left side exist */
		{
			ptTempTree = (*ptTreePoint)->left;
			if((*ptTreePoint)->top != NULL)		/* Not Root Point */
			{
				/* deleate right side */
				(*ptTreePoint) = (*ptTreePoint)->top;
				free((*ptTreePoint)->right);
				(*ptTreePoint)->right = ptTempTree;
				ptTempTree->top = *ptTreePoint;
			}
			else
			{
				/* set left side to  Root */
				free((*ptTreePoint));
				*ptTreePoint = ptTempTree;
				(*ptTreePoint)->top = NULL;
			}
		}
		else
		{
			if((*ptTreePoint)->top != NULL)		/* Not Root Point */
			{
				(*ptTreePoint) = (*ptTreePoint)->top;
				free((*ptTreePoint)->right);
				(*ptTreePoint)->right = NULL;
				if((*ptTreePoint)->left != NULL)
				{
					ExchangeTreePoint(ptTreePoint, LEFT_POINT);
				}
			}
			else 	/* deleate Root Point */
			{
				free(*ptTreePoint);
				*ptTreePoint = NULL;
			}
		}
	}
}

static void ExchangeTreePoint(TreePoint_t **ptTreePoint, int direct)
{
	TreePoint_t * ptOldTopTree;
	TreePoint_t * ptNewTopTree;
	TreePoint_t * ptTempTree;
	TreePoint_t * ptTopTree;
	
	if((*ptTreePoint) != NULL)
	{
		/* exchange point */
		if(direct == RIGHT_POINT)
		{
			/* right is new Top tree */
			ptNewTopTree = (*ptTreePoint)->right;
			ptOldTopTree = (*ptTreePoint);
			
			/* change Tree top */
			ptNewTopTree->top = ptOldTopTree->top;
			ptTempTree = ptNewTopTree->left;
			if(ptTempTree != NULL)
			{
				while(ptTempTree->left != NULL)
				{
					ptTempTree = ptTempTree->left;
				}
				ptTempTree->left = ptOldTopTree;
			}
			else
			{
				ptNewTopTree->left = ptOldTopTree;
				ptTempTree = ptNewTopTree;
			}
			
			/* change Tree Old Top */
			ptOldTopTree = ptTempTree->left; 
			ptOldTopTree->top   = ptTempTree;
			ptOldTopTree->left  = NULL;
			ptOldTopTree->right = NULL;
		}
		else
		{
			/* left is new Top tree */
			ptNewTopTree = (*ptTreePoint)->left;
			ptOldTopTree = (*ptTreePoint);
			
			/* change Tree New Top */
			ptNewTopTree->top  = ptOldTopTree->top;
			ptTempTree = ptNewTopTree->right;
			
			if(ptTempTree != NULL)
			{
				while(ptTempTree->right != NULL)
				{
					ptTempTree = ptTempTree->right;
				}
				ptTempTree->right = ptOldTopTree;
			}
			else
			{
				ptNewTopTree->right = ptOldTopTree;
				ptTempTree = ptNewTopTree;
			}
			
			/* change Tree Old Top */
			ptOldTopTree = ptTempTree->right;
			ptOldTopTree->top   = ptTempTree;
			ptOldTopTree->left  = NULL;
			ptOldTopTree->right = NULL;
			
		}
		
		if(ptNewTopTree->top != NULL)
		{
			ptTempTree = ptNewTopTree->top;
			if(ptTempTree->key > ptNewTopTree->key)
			{
				ptTempTree->left = ptNewTopTree;
			}
			else
			{
				ptTempTree->right = ptNewTopTree;
			}
		}
		(*ptTreePoint) = ptNewTopTree;
	}
	else
	{
		/* error point */
	}
}


/* This Search is FIFO Argorithm */
static void AllFreeProcess(TreePoint_t **ptTreePoint)
{
	TreePoint_t  * ptTempTree;
	while((*ptTreePoint) != NULL) 						 	/* until All Free */
	{
		if((*ptTreePoint)->left != NULL) 			 	/* Left side not NULL */
		{
			(*ptTreePoint) = (*ptTreePoint)->left;	 	/* Search Left Side */
		}
		else if((*ptTreePoint)->right != NULL) 		 	/* Right side not NULL */
		{
			(*ptTreePoint) = (*ptTreePoint)->right;  	/* Search Right Side */
		}
		else
		{
			if((*ptTreePoint)->top != NULL)				/* Both Side is NULL */
			{
				(*ptTreePoint) = (*ptTreePoint)->top;	/* back to top */
				if((*ptTreePoint)->left != NULL)		/* left side is not NULL */
				{
					free((*ptTreePoint)->left);			/* free left side */
					(*ptTreePoint)->left = NULL;
				}
				else									/* right side is not NULL */
				{
					free((*ptTreePoint)->right);		/* free right side */
					(*ptTreePoint)->right = NULL;
				}
			}
			else
			{
				free(*ptTreePoint);						/* free Root Point */
				(*ptTreePoint) = NULL;
			}
		}
	}
}


