#include <cstdio>
#include <cstdlib>
#include <string>
#include <ctime>
#define rnd (rand()-1)
struct nod { bool end; nod *n[2];};

typedef nod* trie;
trie T;

void init()
{
  srand(time(0));
  T=new nod;
  memset(T->n, 0, sizeof(T->n));
  T->end=0;
}

void insert(trie &n, int v)
{
  //printf("%d\n", v);
 
  if(!n->n[v&1])
    {
      n->n[v&1]=new nod;
      memset(n->n[v&1], 0, sizeof(n));
      n->end=0;
    }
  
  if(!(v>>1))
    {
      n->end=1;
      return ;
    }
  insert(n->n[v&1], (v>>1));
}

int find(trie n, int v)
{
  //  printf("%d\n", v);
  if(!(v>>1))
    if(n->n[v&1] && n->end)return 1;
    else return 0;

  if(n->n[v&1]) return find(n->n[v&1], v>>1);
  return 0;
}


int main()
{
  init();
  insert(T, 23423);
  insert(T, 12323);
  insert(T, 23);

  printf("%d %d\n", find(T, 23423), find(T, 2342));
  printf("%d\n", find(T,12323));
  printf("%d %d\n", find(T,21), find(T,23));
  //printf("%d %d\n", find(T,23), find(T, 21));
  int i, n=100000;
  for(i=1;i<=n;++i) insert(T, rnd);

  return 0;
}