//Dumea Eduard Constantin, grupa 134
 
#include<iostream>
#include<fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
 
using namespace std;
 
class Functie
{
private:
    int a , b;
    int mod;
    int size;
public:
    Functie(int &);
    void generare_parametri();
    int functie(int&);
    int functie(unsigned int&);
    int functie(float&);
    int functie(double&);
    int functie(char&);
    int functie(string&);
};
  
Functie::Functie(int &n)
{   
    size = n;
    generare_parametri();
}
  
void Functie::generare_parametri()
{
    int pr[]={666013, 666011, 597471, 579347};
    a = rand() % 1000000+10;
    b = rand() % 1030000+10;
    mod = pr[rand () % 5];
}
  
int Functie::functie(char &val)
{
    int poz;
    poz = ((a + b*val ) % mod) % size;
    return poz;
}
  
int Functie::functie(int &val)
{
    int poz;
    poz=((a + b*val ) % mod) % size;
    return poz;
}
 
int Functie::functie(unsigned int &val)
{
    int poz;
    poz=((a + b*val ) % mod) % size;
    return poz;
}
  
int Functie::functie(float &val)
{
    int poz;
    while ((val - (int)val) != 0)
    {
        val *= 10;
        if (val > size)
        {
            val -= size;
        }
    }
    poz = (((long)a + (long)b*(long)val ) % (long)mod) % (long)size;
    return poz;
}
  
int Functie::functie(double &val)
{
    int poz;
    while ((val - (int)val) != 0)
    {
        val *= 10;
        if (val > size)
        {
            val -= size;
        }
    }
    poz = (((long)a + (long)b*(long)val ) % (long)mod) % (long)size;
    return poz;
}
  
int Functie::functie(string &val)
{
    int aux = 0;
    for (int i =0;i<val.size();i++)
        aux = (aux+a + b*val[i])%size; 
    return aux;
}
 
 
 
template<class type>
class Basic_Hash
{
  
public:
    virtual bool operator+=(type &)=0;
    virtual void operator-=(type &)=0;
    virtual bool operator==(type &)=0;
    virtual void Initializare()=0;
    bool Rezolvare();
  
};
template<class type>
bool Basic_Hash<type>::Rezolvare()
{
    int n, op, i, ok=0;
    type x;
     
    srand( time( NULL ) );
     
    
    while(ok==0)
    {
        Initializare();
         
		 cout<<"da ";
		 
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
         
        f>>n;
         
        ok=1;
     
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>x;
         
            if(op==1)
                ok = *this += x;
            else
                if(op==2)
                    *this -= x;
                else
                    g<<(*this==x)<<"\n"; 
        }
         
        f.close();
        g.close();
         
    }
  
}
  
  
  
template<class type>
class Cuckoo_Hash:public Basic_Hash<type>
{
    int size;
    type *hash1, *hash2;
    bool *viz1, *viz2;
    Functie *func1, *func2;
  
    public:
    Cuckoo_Hash<type>(unsigned int);
    ~Cuckoo_Hash<type>();
    void Initializare();
    bool operator += (type &);
    void operator -= (type &);
    bool operator == (type &);
};
  
template<class type>
Cuckoo_Hash<type>::Cuckoo_Hash(unsigned int n)
{
    size = n;
     
    hash1 = new type[size];
    hash2 = new type[size];
     
    func1 = new Functie(size);
    func2 = new Functie(size);
     
    viz1 = new bool[size];
    viz2 = new bool[size];
  
    //fill(viz1,viz1+size,0);
    //fill(viz2,viz2+size,0);
}
  
template<class type>
Cuckoo_Hash<type>::~Cuckoo_Hash()
{
    delete[] hash1;
    delete[] hash2;
    delete[] viz1;
    delete[] viz2;
    delete func1;
    delete func2;
}
 
 
template<class type>
bool Cuckoo_Hash<type>::operator+=(type &val)
{
    int nr=0, poz1, poz2;
    type aux;
     
    poz1 = func1->functie(val);
    poz2 = func2->functie(val);
     
    if( (hash1[poz1]==val && viz1[poz1] ==1 ) || ( hash2[poz2]==val && viz2[poz2]==1 ) )
        return 1;
     
    if(viz1[poz1]==0)
    {
        hash1[poz1]=val;
        viz1[poz1]=1;
        return true;
    }
    else
        if(viz2[poz2]==0)
        {
            hash2[poz2]=val;
            viz2[poz2]=1;
            return true;
        }
        else
        {
            aux = val;
            val = hash1[poz1];
            hash1[poz1] = aux;
        }
     
    while(nr<30)
    {
        nr++;
         
        poz2 = func2->functie(val);
         
        if(viz2[poz2]==0)
        {
            hash2[poz2]=val;
            viz2[poz2]=1;
            return 1;
        }
        else
        {
            poz1 = func1->functie(hash2[poz2]);
            aux=hash2[poz2];
            hash2[poz2]=val;
            val=hash1[poz1];
            hash1[poz1]=aux;
        }
    }
     
    return false;
}
template<class type>
void Cuckoo_Hash<type>::operator-=(type &val)
{
    int poz1, poz2;
     
    poz1 = func1->functie(val);
    poz2 = func2->functie(val);
     
    if( ( hash1[poz1] == val ) && viz1[poz1] == 1 )
        viz1[poz1]=0;
         
    else
        if( hash2[poz2] == val && viz2[poz2] == 1 )
            viz2[poz2] = 0;
}
template<class type>
bool Cuckoo_Hash<type>::operator==(type &val)
{
    int poz1, poz2;
     
    poz1= func1->functie(val);
    poz2= func2->functie(val);
     
    if( ( hash1[poz1] == val && viz1[poz1] == 1) || ( hash2[poz2] == val && viz2[poz2] == 1) )
        return 1;
    else
        return 0;
}
  
template<class type>
void Cuckoo_Hash<type>::Initializare()
{
    fill(viz1,viz1+size,0);
    fill(viz2,viz2+size,0);
    func1->generare_parametri();
    func2->generare_parametri();
}
 
template<class type>
class Chaining_Hash:public Basic_Hash<type>
{
	int size, nr;
	type *v;
	vector<unsigned int> hash[666013];
    Functie *func;
  
public:
    Chaining_Hash(unsigned int);
    ~Chaining_Hash();
    bool operator+=(type &);
    void operator-=(type &);
    bool operator==(type &);
    void Initializare();
};
  
template<class type>
Chaining_Hash<type>::Chaining_Hash(unsigned int x)
{
    int i;
    size = x;
	v=new type[size+1];
    func = new Functie(size);
}
  
template<class type>
Chaining_Hash<type>::~Chaining_Hash()
{
   delete[] v;
   delete func;
}
template<class type>
bool Chaining_Hash<type>::operator+=(type &val)
{
	vector<unsigned int>::iterator it;
    int poz, i;
    poz= func->functie(val);
	v[++nr]=val;
	
	for(it=hash[poz].begin();it!=hash[poz].end();it++)
		if(v[*it]==val) 
			return true;
		
	hash[poz].push_back(nr);
	return true;
}
template<class type>
void Chaining_Hash<type>::operator-=(type &val)
{
    int poz, i;
	vector<unsigned int>::iterator it;
    poz = func->functie(val);
	
	for(it=hash[poz].begin();it!=hash[poz].end();it++)
		if(v[*it]==val) 
			break;

	if(it!=hash[poz].end())
	{
		*it=hash[poz].back();
		hash[poz].pop_back();
	}
}
template<class type>
bool Chaining_Hash<type>::operator==(type &val)
{
     int poz, i;
	 vector<unsigned int>::iterator it;
     poz = func->functie(val);
  
	for(it=hash[poz].begin();it!=hash[poz].end();it++)
		if(v[*it]==val) 
			return true;
  
    return false;
}
  
template<class type>
void Chaining_Hash<type>::Initializare()
{
    int i;
	
	nr=0;
	
    func->generare_parametri();
}
  
  

int main()
{
	int alg=1;
	
	Basic_Hash <unsigned int> *h;
	/*
	
	cout<<"tastati 1 pentru Chaining_Hash sau 2 pentru Cuckoo_Hash: ";
	cin>>alg;
	
	while(alg!=1&&alg!=2)
	{
		cout<<"nu ati indrodus o valoare corecta. Tastati 1 sau 2: ";
		cin>>alg;
	}
	x=1
	*/
		
	if(alg==1)
		h = new Chaining_Hash<unsigned int>(1000000);
	else
		h = new Cuckoo_Hash<unsigned int>(1000000);

 
	 
    h->Rezolvare ();

    return 0;
 
}