// Constantin Maria - grupa 134

#include<fstream>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include<iostream>

using namespace std;

class Hash_Func
{
    int MOD;
    int a,b,c;
    int size_h;
public:
    Hash_Func(int&);
    void Generate();
    int Hash(int&);
    int Hash(unsigned int&);
    int Hash(char&);
    int Hash(double&);
    int Hash(float&);
    int Hash(string&);
};
Hash_Func::Hash_Func(int &size)
{
    size_h = size;
    Generate();
}
void Hash_Func::Generate()
{
    int mo[]={999983,999979,999961,999953,999917};
    int dif;
    dif = size_h - 1000000;
    a = rand () % 10000019 + 1;
    b = rand () % 20008903 + 1;
    c = rand () % 100801 + 1;
    MOD = mo[rand () % 5] + dif;
}
int Hash_Func::Hash(int &x)

{

    return (a * x * x + c * x + b) % MOD;;
}
int Hash_Func::Hash(char &x)

{
    return (a * x * x + c * x + b) % MOD;
}
int Hash_Func::Hash(unsigned int &x)

{
    return (a * x * x + c * x + b) % MOD;
}
int Hash_Func::Hash(double &x)

{
    return ((int)(a * x) + b + c * c) % MOD;
}
int Hash_Func::Hash(float &x)

{
    return ((int)(a * x) + b + c * c) % MOD;
}
int Hash_Func::Hash(string &x)

{
    int i,val=0;
    for( i=0; i < x.size(); i++ )
    {
        val = ( (val*256) + (int)x[i] ) % MOD;
    }
    return abs((a * val + b + c*c) % MOD);
}

template<class T>
class Basic_Hash
{

public:
    virtual bool operator+=(T)=0;
    virtual void operator-=(T)=0;
    virtual bool operator==(T)=0;
    virtual void Rehash()=0;
    bool Citeste();

};
template<class T>
bool Basic_Hash<T>::Citeste ()
{
    int n, caz, i;
    T x;

    ifstream fin("hashuri.in");
    ofstream fout("hashuri.out");
    fin>>n;
    for (i = 1; i <= n ; i++)
    {
        fin>> caz>> x;

        switch (caz)
        {
            case 1: if(!(*this+=x))return 0;break;
            case 2: *this-=x; break;
            case 3: fout <<(*this==x)<<"\n"; break;

        }
    }
    fin.close();
    fout.close();
    return 1;

}



template<class T>
class Cuckoo_Hash:public Basic_Hash<T>
{
    T *h1, *h2;
    int size_h;
    bool *viz1, *viz2;
    Hash_Func *F1,*F2;

public:
    bool operator+=(T);
    void operator-=(T);
    bool operator==(T);
    void Rehash();
    Cuckoo_Hash(unsigned int);
    ~Cuckoo_Hash();

};

template<class T>
Cuckoo_Hash<T>::Cuckoo_Hash(unsigned int s)
{
    size_h = s;
    h1 = new T[size_h];
    h2 = new T[size_h];
    F1 = new Hash_Func(size_h);
    F2 = new Hash_Func(size_h);
    viz1 = new bool[size_h];
    viz2 = new bool[size_h];
    fill(viz1, viz1 + size_h, false);
    fill(viz2, viz2 + size_h, false);
}

template<class T>
Cuckoo_Hash<T>::~Cuckoo_Hash()
{
   delete[] h1;
   delete[] h2;
   delete F1;
   delete F2;
   delete[] viz1;
   delete[] viz2;
}
template<class T>
bool Cuckoo_Hash<T>::operator+=(T x)
{
    int ok = 0, st = 1,v1,v2;
    T aux;

    v1 = F1->Hash(x);
    v2 = F2->Hash(x);

    while( ok > -30 )
    {
        if( st == 1 )
        {
            if( !viz1[v1] || h1 [v1] == x)
            {
                h1 [v1] = x;
                viz1[v1] = true;
                return true;
            }
            else
            {
                st = -1;
                if( ok < 0)
                {
                    aux = x;
                    x =  h1 [v1];
                    h1 [v1] = aux;
                    v1 = F1->Hash(x);
                    v2 = F2->Hash(x);
                }
            }
        }
        if( st == -1)
        {
            if(!viz2[v2] || h2 [v2] == x)
            {

                h2 [v2] = x;
                viz2 [v2] = true;
                return true;
            }

            else
            {
                st = 1;
                if( ok < 0)
                {
                    aux = h2[v2];
                    h2[v2] = x;
                    x = aux;
                    v1 = F1->Hash(x);
                    v2 = F2->Hash(x);

                }
            }
        }
        ok--;
    }
    return false;
}
template<class T>
void Cuckoo_Hash<T>::operator-=(T x)
{
    int v1,v2;
    v1 = F1->Hash(x);
    v2 = F2->Hash(x);
    if(viz1[v1] && h1[v1] == x) viz1[v1]=false;

        else if(viz2[v2] && h2[v2] == x ) viz2[v2] = false;
}
template<class T>
bool Cuckoo_Hash<T>::operator==(T x)
{
     int v1 = F1->Hash(x);
     int v2 = F2->Hash(x);

     if(viz1[v1] && h1 [v1] == x) return true;

     if(viz2[v2] && h2 [v2] == x ) return true;

    return false;
}

template<class T>
void Cuckoo_Hash<T>::Rehash()
{
    fill(viz1, viz1 + size_h, false);
    fill(viz2, viz2 + size_h, false);
    F1->Generate();
    F2->Generate();
}
template<class T>
class Chaining_Hash:public Basic_Hash<T>
{public:
    struct nod
    {
        T inf;
        nod *next;
    };
private:
    nod **h1;
    int *h2;
    int size_h;
    Hash_Func *F1;

public:
    bool operator+=(T);
    void operator-=(T);
    bool operator==(T);
    void Rehash();
    Chaining_Hash(unsigned int);
    ~Chaining_Hash();

};

template<class T>
Chaining_Hash<T>::Chaining_Hash(unsigned int s)
{
    int i;
    size_h = s;
    h1 = new nod*[size_h];
    h2 = new int[size_h];
    F1 = new Hash_Func(size_h);
    for(i = 0; i < size_h; i++)
    {
        h2[i] = 0;
        h1[i] = NULL;
    }

}

template<class T>
Chaining_Hash<T>::~Chaining_Hash()
{
   delete[] h1;
   delete[] h2;
   delete F1;
}
template<class T>
bool Chaining_Hash<T>::operator+=(T x)
{
    int v1;
    v1 = F1->Hash(x);
    if( h2[v1] > 100 ) return 0;

    if(!(*this==x))
    {
        nod *aux;
        aux = new nod;
        aux->inf = x;
        aux->next = h1[v1];
        h1[v1] = aux;
        h2[v1]++;
        return 1;
    }

}
template<class T>
void Chaining_Hash<T>::operator-=(T x)
{
    int v1;
    v1 = F1->Hash(x);
    if(h2[v1]==0)return;
    nod *p;
    if(h1[v1]-> inf == x)
        {
            p = h1[v1];
            h1[v1] = h1[v1]->next;
            h2[v1]--;
            delete p;

        }
        else
        {
            for(p = h1[v1]; p->next;)
                if(p->next->inf == x)
                {
                    nod *aux;
                    aux = p->next;
                    p->next = aux->next;
                    delete aux;
                    h2[v1]--;
                }
                    else p = p->next;
        }


}
template<class T>
bool Chaining_Hash<T>::operator==(T x)
{
     int v1 = F1->Hash(x);
     nod *p;

    for(p = h1[v1]; p; p = p->next)
        if(p->inf == x) return true;

    return false;
}

template<class T>
void Chaining_Hash<T>::Rehash()
{
    int i;
    for(i = 0; i < size_h; i++)
    {
        h2[i] = 0;
        h1[i] = NULL;
    }
    F1->Generate();
}


int main()
{


    srand (time(NULL));
    int x;
    Basic_Hash <unsigned int> *H;
   //cout<<"Alege functia de Hash dorita:\n1 = Cuckoo Hash\n2 = Chaising Hash\n";
    //cin>>x;
    x=2;
    switch(x)
    {
        case 1: H = new Cuckoo_Hash<unsigned int>(1000000);break;
        case 2: H = new Chaining_Hash<unsigned int>(1000000); break;
    }


    while(!H->Citeste ())
    {
        H->Rehash();
    }
    return 0;

}