#include <bits/stdc++.h>

//using std::string;
using std::cerr;

const char code[2][2] = {"0", "1"};

class string {
public:
  char *s;
public:
  string() {
    s = NULL;
  }

  string(const char *s) {
    this -> s = new char[strlen(s)];
    strcpy(this -> s, s);
  }

  bool operator < (string other) {
    return strcmp(this -> s, other.s) < 0;
  }

  bool operator > (string other) {
    return strcmp(this -> s, other.s) > 0;
  }

  bool operator == (string other) {
    return strcmp(this -> s, other.s) == 0;
  }
};

/** 
  Treap = 
  Arbore binar de cautare + MaxHeap.
            |                  |
        pentru chei    pentru prioritati
**/
struct treap {
  string key;
  int priority;
  treap *left;
  treap *right;

  treap() {
  
  }

  treap(string key, int priority, treap *left, treap *right) {
    this -> key = key;
    this -> priority = priority;
    this -> left = left;
    this -> right = right;
  }
};

treap *root, *NIL;

/** Initializeaza treap-ul. **/
void init() {
  string empty;
  srand(unsigned(time(NULL)));
  NIL = new treap{empty, 0, NULL, NULL};
  root = NIL;
}

/** Roteste la stanga. **/
void rotLeft(treap* &node) {
  treap *tmp = node -> left;
  node -> left = tmp -> right;
  tmp -> right = node;
  node = tmp;
}

/** Roteste la dreapta. **/
void rotRight(treap* &node) {
  treap *tmp = node -> right;;
  node -> right = tmp -> left;
  tmp -> left = node;
  node = tmp;
}

/** Balanseaza, mentinand echilibrat treap-ul. **/
void balance(treap* &node) {
  if (node -> left -> priority > node -> priority) {
    rotLeft(node);
  } else if (node -> right -> priority > node -> priority) {
    rotRight(node);
  }
}

/** Adauga in treap cheia "key" cu prioritatea "priority". **/
void insert(treap* &node, string key, int priority) {
  if (node == NIL) {
    node = new treap(key, priority, NIL, NIL);
    return;
  }
  if (key < node -> key) {
    insert(node -> left, key, priority);
  } else if (node -> key < key) {
    insert(node -> right, key, priority);
  }
  balance(node);
}

/** Sterge din treap cheia "key". **/
void erase(treap* &node, string key) {
  if (node == NIL) {
    return;
  }
  if (key < node -> key) {
    erase(node -> left, key);
  } else if (node -> key < key) {
    erase(node -> right, key);
  } else {
    if (node -> left == NIL && node -> right == NIL) {
      node = NIL;
    } else {
      if (node -> left -> priority > node -> right -> priority) {
        rotLeft(node);
      } else {
        rotRight(node);
      }
      erase(node, key);
    }
  }
}

/** Cauta cheia "key" in treap. **/
int search(treap* &node, string key) {
  if (node == NIL) {
    return 0;
  }
  if (key == node -> key) {
    return 1;
  }
  if (key < node -> key) {
    return search(node -> left, key);
  } else {
    return search(node -> right, key);
  }
}

void dump(treap* &node) {
  if (node == NIL) {
    return;
  }
  dump(node -> left);
  cerr << node -> key.s << "\n";
  dump(node -> right);
}

int main(void) {
  /*
  int N, task, x;
  FILE *f = fopen("hashuri.in", "r");
  freopen("hashuri.out", "w", stdout);

  init();

  fscanf(f, "%d", &N);
  while (N) {
    fscanf(f, "%d %d", &task, &x);
    if (task == 1) {
      insert(root, x, rand() + 1);
    } else if (task == 2) {
      erase(root, x);
    } else {
      puts(code[search(root, x)]);
    }
    N--;
  }
  fclose(f);
  fclose(stdout);
  */

  init();

  insert(root, string("tochter"), rand() + 1);
  insert(root, string("onkel"), rand() + 1);
  insert(root, string("vater"), rand() + 1);
  insert(root, string("mutter"), rand() + 1);
  insert(root, string("vetter"), rand() + 1);
  insert(root, string("kusine"), rand() + 1);

  dump(root);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}