using namespace std;
#include <cstdio>
#include <string>
#include <cstdlib>
#include <ctime>
#include <set>
#define oo 0x3f3f3f3f
#define maxn 666791
#define rnd (rand()-1)
struct nod { int v, p; nod*l, *r;};

nod *H[maxn];
nod *nil;
typedef nod* tree;

inline int hash(int v)
{
  return v%maxn;
}

void init()
{
  srand(time(0));
  nil=new nod;
  nil->p=nil->v=-oo;
  nil->l=nil->r=0;
  for(int i=0;i<maxn;++i) H[i]=nil;
}

inline void rotl(tree &n)
{
  nod*p=n->l;
  n->l=p->r;
  p->r=n;
  n=p;
}
inline void rotr(tree &n)
{
  nod*p=n->r;
  n->r=p->l;
  p->l=n;
  n=p;
}


void insert(tree &n, int v)
{
  if(n==nil)
    {
      n=new nod;
      n->v=v;
      n->p=rnd;
      n->l=n->r=nil;
      return;
    }
 
  if(v>n->v)
    {
      insert(n->r, v);
      if(n->r->p>n->p) rotr(n);
    }
  if(v<n->v)
    {
      insert(n->l, v);
      if(n->l->p>n->p)rotl(n);
    }
}

int find(tree n, int v)
{
  if(n==nil)return 0;
  if(v>n->v) return find(n->r, v);
  if(v<n->v) return find(n->l, v);
  return 1;
}


inline void insrt(int v)
{
  insert(H[hash(v)], v);
}

inline int fnd(int v)
{
  return find(H[hash(v)], v);
}


int main()
{
  init();
  
  insrt(4);
  insrt(12);
  insrt(32);

  printf("%d %d %d\n", fnd(4), fnd(5), fnd(12));

  int n=1000000, i;
  // printf("%d\n", rnd%2000000000);
  int t=666791;
  int s=t;
   for(i=1;i<=n;++i) insrt(s), s+=t, s%=1000000000;
   for(i=1;i<=n;++i) fnd(i);
  //  for(i=1;i<=n;++i) insert(H[1], rnd);
  //set<int>a;
  //for(i=1;i<=n;++i) a.insert(rnd); 
 return 0;


}