#include <cstdio>
#include <cstdlib>
#include <ctime>
#define maxn (1<<18)

struct nod { int v; nod *n;};

nod *H1[maxn], *H2[maxn];
int len1[maxn], len2[maxn];
int r1, r2;

inline void init()
{
  srand(time(0));
  r1=(rand()<<1)|1;
  r2=(rand()<<1)|1;
}

inline int hash1(int v)
{
  return (unsigned) (v*r1)>>14;
}
inline int hash2(int v)
{
  return (unsigned) (v*r2)>>14;
}


inline void insert(int v)
{
  int h1=hash1(v);
  int h2=hash2(v);
  nod *p=new nod;
  p->v=v;

  if(len1[h1]<len2[h2])
    {
      ++len1[h1];
      p->n=H1[h1];
      H1[h1]=p;
    }
  else
    {
      ++len2[h2];
      p->n=H2[h2];
      H2[h2]=p;
    }
}

inline int find(int v)
{
  nod *p;
  int h=hash1(v);
  for(p=H1[h]; p ; p=p->n)
    if(p->v==v)return 1;
  h=hash2(v);
  for(p=H2[h]; p ; p=p->n)
    if(p->v==v) return 1;
  return 0;
}

int main()
{
  init();

  //  insert(3), insert(9), insert(21);
  // printf("%d %d %d\n", find(3), find(8), find(21));
  int i, n=1000000;
  for(i=1;i<=n;++i) insert(rand());
  for(i=1;i<=n;++i) find(rand());
  return 0;
}