/** Clasa pentru trie pe biti.
 * Urmeaza: priority_queue + k-th element.
**/
#include <stdio.h>

template <const int MAX_BIT> class trie {
  #define NIL -1
private:
  struct node {
    node* son[2];

    node() {
      son[0] = son[1] = NULL;
    }
  } *root;

  void push(node* curr, int x, int bit) {
    if (bit == NIL) {
      return;
    }
    int next = (x >> bit) & 1;
    if (curr -> son[next] == NULL) {
      curr -> son[next] = new node;
    }
    push(curr -> son[next], x, bit - 1);
  }

  bool pop(node* curr, int x, int bit) {
    if (bit == NIL) {
      return true;
    }
    int next = (x >> bit) & 1;
    if (pop(curr -> son[next], x, bit - 1)) {
      curr -> son[next] = NULL;
    }
    return curr != root && curr -> son[0] == NULL && curr -> son[1] == NULL;
  }

  bool find(node* curr, int x, int bit) {
    if (bit == NIL) {
      return true;
    }
    int next = (x >> bit) & 1;
    if (curr -> son[next] == NULL) {
      return false;
    }
    return find(curr -> son[next], x, bit - 1);
  }
public:
  trie() {
    root = new node;
  }

  inline void insert(int x) {
    push(root, x, MAX_BIT - 1);
  }

  inline void erase(int x) {
    pop(root, x, MAX_BIT - 1);
  }

  inline bool search(int x) {
    return find(root, x, MAX_BIT - 1);
  }
};

signed main(void) {
  trie <3> my;
  my.insert(3);
  my.insert(2);
  my.insert(7);
  my.insert(6);
  fprintf(stderr, "%d\n", my.search(3));
  fprintf(stderr, "%d\n", my.search(7));
  my.erase(2);
  fprintf(stderr, "%d\n", my.search(2));

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