s

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

typedef struct Node Node;

struct Node
{
  int key, count;
  char *value;
  Node *parent, *left, *right;
};
Node *tree_find_node(Node *root, int key)
{
  Node *node = root;
  while(node && node->key != key)
  {
    if(key < node->key) node = node->left;
    else node = node->right;
  }
  return node;
}

void tree_insert( Node **root, int key, char *value)
{
  Node *new_node = (Node *)malloc(sizeof(Node));
  new_node->key = key;
  new_node->value = value;
  new_node->count = 0;
  new_node->parent = NULL; new_node->left = NULL; new_node->right = NULL;

  if(!*root)
  {
    *root = new_node;
    return;
  }

  Node *node = *root;
  for(unsigned char k = 0; k < 300; k++)
  {
    node->count++;
    if(key < node->key)
    {
      if(!node->left)
      {
        node->left = new_node;
        new_node->parent = node;
        break;
      }
      node = node->left;
    }
    else
    {
      if(!node->right)
      {
        node->right = new_node;
        new_node->parent = node;
        break;
      }
      node = node->right;
    }

  }
}

void replace_node(Node **root, Node *x, Node *y)
{
  if(*root == x)
  {
    *root = y;
    if(y) y->parent = NULL;
  }
  else
  {
    Node *parent = x->parent;
    if(y) y->parent = parent;

    if(parent->left == x) parent->left = y;
    else parent->right = y;
  }
}

Node *minimum(Node *node)
{
  if(!node) return NULL;
  else
  {
    while(node->left)
    {
      node->count--;
      node = node->left;
    }
    return node;
  }
}

Node *succ(Node *node)
{
  if(node->right)
  {
    return minimum(node->right);
  }
  else
  {
    Node *node_ = node->parent;
    while(node_ && node == node_->right)
    {
      node = node_;
      node_ = node_->parent;
    }
    return node_;
  }
}

void delete(Node **root, int key)
{
  Node *node = tree_find_node(*root, key);
  Node *tr = *root;
  while(tr && tr->key != key)
  {
    tr->count--;
    if(key < tr->key) tr = tr->left;
    else tr = tr->right;
  }

  if(!node->left && !node->right) replace_node(root, node, NULL);
  else if(!node->left) replace_node(root, node, node->right);
  else if(!node->right) replace_node(root, node, node->left);
  else
  {
    Node *y = succ(node);
    replace_node(root, y, y->right);
    node->left->parent = y;
    y->left = node->left;
    if(node->right) node->right->parent = y;
    y->right = node->right;
    y->count = node->count - 1;
    replace_node(root, node, y);
  }
  free(node->value);
  free(node);
}

Node *search(Node *root, int rank)
{
  Node *node = root;
  while(node)
  {
    if(node->left)
    {
        if(node->left->count == rank - 1) return node;
      else if(node->left->count > rank - 1) node = node->left;
      else
      {
        rank -= node->left->count + 2;
        node = node->right;
      }
    }
    else
    {
      if(rank)
      {
        rank--;
        node = node->right;
      }
      else return node;
    }
  }
}
struct Task {
    Node *node;
};
typedef struct Task task;
struct stack {
    task *data;
    int cap, top;
};

void init(struct stack *stk, int n)
{
    stk->data = malloc(sizeof(task) * n);
    stk->top = 0;
    stk->cap = n;
}
void push(struct stack *stk, task l)
{
    if(stk->top == stk->cap) printf("STACK IS FULL");
    stk->data[stk->top] = l;
    stk->top++;
}
int stackempty(struct stack *stk)
{
    if(stk->top == 0) return 1;
    else return 0;
}
task pop(struct stack *stk)
{
    task x;
    if(stackempty(stk)) printf("Here we go again :)");
    else
    {
    	stk->top--;
    	x = stk->data[stk->top];
    }
    return x;
}
int main()
{
  int n;
  scanf("%d", &n);
  Node *root = NULL;
  char action[7], *word;
  for(int i = 0; i < n; i++)
  {
    scanf("%s", action);
    int x;
    scanf("%d", &x);
    if(strcmp("INSERT", action) == 0)
    {

        word = (char *)malloc(sizeof(char) * 10);
        scanf("%s", word);
        tree_insert(&root, x, word);
    }
    if(strcmp("SEARCH", action) == 0)

        printf("%s\n", search(root, x)->value);

    if(strcmp("LOOKUP", action) == 0)
      printf("%s\n", tree_find_node(root, x)->value);

    if(strcmp("DELETE", action) == 0)
        delete(&root, x);
  }

  struct stack tasks;
	task t;
	t.node = root;
	init(&tasks,n);
	push(&tasks,t);
	while(!stackempty(&tasks))
	{
		t = pop(&tasks);
		if(t.node)
		{
		task t1;
		if(t.node->left)
    {
      t1.node = t.node->left;
		  push(&tasks,t1);
    }
    if(t.node->right)
    {
      t1.node = t.node->right;
      push(&tasks,t1);
    }
		free(t.node);
		}
	}
  free(tasks.data);
  return 0;
}