//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[]={999983,999979,899981,900007,800011};
    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();
		
		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>
{public:
    typedef struct nod
    {
        type x;
        nod *urm;
    }lista;
private:
    lista **hash1;
    int *hash2;
    int size;
    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;
    hash1 = new lista*[size];
    hash2 = new int[size];
    func = new Functie(size);
    for(i = 0; i < size; i++)
    {
        hash2[i] = 0;
        hash1[i] = NULL;
    }
 
}
 
template<class type>
Chaining_Hash<type>::~Chaining_Hash()
{
   delete[] hash1;
   delete[] hash2;
   delete func;
}
template<class type>
bool Chaining_Hash<type>::operator+=(type &val)
{
    int poz;
    poz= func->functie(val);
    if( hash2[poz] > 100 ) 
		return 0;
 
    if(!(*this==val))
    {
        lista *aux;
        aux = new lista;
        aux->x = val;
        aux->urm = hash1[poz];
        hash1[poz] = aux;
        hash2[poz]++;
        return 1;
    }
 
}
template<class type>
void Chaining_Hash<type>::operator-=(type &val)
{
    int poz;
    poz = func->functie(val);
    if(hash2[poz]==0)
		return;
	
    lista *p;
    if(hash1[poz]-> x == val)
        {
            p = hash1[poz];
            hash1[poz] = hash1[poz]->urm;
            hash2[poz]--;
            delete p;
 
        }
        else
        {
            for(p = hash1[poz]; p->urm;)
                if(p->urm->x == val)
                {
                    lista *aux;
                    aux = p->urm;
                    p->urm = aux->urm;
                    delete aux;
                    hash2[poz]--;
                }
                    else p = p->urm;
        }
 
 
}
template<class type>
bool Chaining_Hash<type>::operator==(type &val)
{
     int poz;
	 poz = func->functie(val);
     lista *p;
 
    for(p = hash1[poz]; p; p = p->urm)
        if(p->x == val) 
			return true;
 
    return false;
}
 
template<class type>
void Chaining_Hash<type>::Initializare()
{
    int i;
    for(i = 0; i < size; i++)
    {
        hash2[i] = 0;
        hash1[i] = NULL;
    }
    func->generare_parametri();
}
 
 
 
int main()
{
	
	Basic_Hash <unsigned int> *h;
	

	h = new Chaining_Hash<unsigned int>(1000000);
 
	 
    h->Rezolvare ();

    return 0;
 
}