#include <cstdio>
#include <cstdlib>
#include <ctime>
#define mod 666123

struct nod { int x; nod *next;};

nod *H[mod+2];
int r;
void init()
{
  time_t s;
  time(&s);

  srand(s%mod);
  r=rand()%997;
  printf("%d\n", r);
}
inline int modulo(int a, int b)
{
  while(a>=b) a-=b;
  return a;
}

inline int hash(int val)
{
  // int t=val;
  //while(t>=mod) t-=mod;
  //int t= (val%mod+r*(val%(mod-7)+1))%mod;
  int t=modulo((modulo(val, mod)+r*(modulo(val, mod-7)+1)), mod); 

  return t;
}


void insert(int val)
{
  int poz=hash(val);//(val%mod +r*(val%(mod-7)+1)))%mod ;

 nod *p=new nod;
  p->x=val;
  p->next=H[poz];
  H[poz]=p;
}

int find(int val)
{
  int poz=hash(val);//(val%mod+r*(val%(mod-7)+1))%mod;
  nod *p;
  for(p=H[poz]; p ;p=p->next)
    if(p->x==val) return 1;
  return 0;
}
void erase(int val)
{
  int poz=hash(val);
  nod *p=H[poz];
  if(p->x==val)
  {
    H[poz]=H[poz]->next;
    delete p;
    return ;
  }
  for(p=H[poz]; p->next ; p=p->next)
    if(p->next->x==val) 
    {
      nod *t=p->next;
      delete t;
      p->next=p->next->next;
      return;
    }
}





int main()
{
  init();
  
  insert(4657);
  
insert(2342);
  insert(3432);
  printf("%d %d\n", find(4657), find(4543));
  printf("%d \n", find(2342));
  printf("%d\n", find(332223));

  for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++) insert(i+j);

  for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++) find(i+j);
/* 
 erase(2342);
  printf("%d\n", find(2342));
  insert(2342);
  printf("%d\n", find(2342));
  printf("%d\n", find(2342));
  printf("%d\n", find(2342));
  erase(2342);
  printf("%d\n", find(2342)); 
*/ return 0;
}