// Constantin Maria - grupa 134

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

using namespace std;
// Functie de Hash - cate una pentru fiecare tabela de Hash
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,899981,900007,800011};
    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);
}
// Clasa de Cuckoo Hash pentru stringuri, dar care e si clasa de baza
class Cuckoo_Hash
{

private:
    list <string> L;
protected:
    int **h1, **h2;
    int size_h;
    bool *viz1,*viz2;
    Hash_Func *F1,*F2;

public:
    virtual bool operator+=(string);
    virtual void operator-=(string);
    virtual bool operator==(string);
    void Citeste();
    Cuckoo_Hash(unsigned int);
    ~Cuckoo_Hash();

};
Cuckoo_Hash::Cuckoo_Hash(unsigned int s)
{
    size_h = s;
    h1 = new int*[size_h];
    h2 = new int*[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);
}
Cuckoo_Hash::~Cuckoo_Hash()
{
   delete[] h1;
   delete[] h2;
   delete F1;
   delete F2;
   delete[] viz1;
   delete[] viz2;
}
void Cuckoo_Hash::Citeste ()
{
    int n, caz, i;
    string x;

    int ok = 0;
    while (ok == 0)
    {
        ok = 1;
        ifstream fin("hashuri.in");
        ofstream fout("hashuri.out");
        fin>>n;
        fill(viz1,viz1+size_h,false);
        fill(viz2,viz2+size_h,false);
        F1->Generate();
        F2->Generate();
        for (i = 1; i <= n && ok; i++)
        {
            fin>> caz>> x;


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

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


}
bool Cuckoo_Hash::operator+=(string x)
{
    int ok = 0, st = 1,v1,v2;

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

    L.push_back(x);
    int *aux;
    aux =(int*)&(L.back());

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

                h2[v2]= aux;
                viz2 [v2] = true;
                return true;
            }
            else
                if(viz2[v2]&&*(string*)h2[v2]==x)return true;
                    else
                    {
                        st = 1;
                        if( ok < 0)
                            {
                                int *auxx;
                                auxx = h2[v2];
                                h2[v2] = aux;
                                aux = auxx;
                                x = *(string*)aux;
                                v1 = F1->Hash(x);
                                v2 = F2->Hash(x);

                            }
                    }
        }
        ok--;
    }
    L.erase(L.begin(),L.end());
    return false;
}
void Cuckoo_Hash::operator-=(string x)
{
    int v1,v2;
    v1 = F1->Hash(x);
    v2 = F2->Hash(x);

    if(viz1[v1] && *(string*)h1[v1] == x) viz1[v1]=false;

        else if(viz2[v2] && *(string*)h2[v2] == x ) viz2[v2] = false;
}
bool Cuckoo_Hash::operator==(string x)
{
     int v1 = F1->Hash(x);
     int v2 = F2->Hash(x);
     if(viz1[v1] && *(string*)h1 [v1] == x) return true;
     if(viz2[v2] && *(string*)h2 [v2] == x ) return true;

    return false;
}
class Cuckoo_Hash_Int:public Cuckoo_Hash
{
    list <int> L;
 public:
     bool operator+=(string);
     void operator-=(string);
     bool operator==(string);
     Cuckoo_Hash_Int(unsigned int s):Cuckoo_Hash(s){};



};
bool Cuckoo_Hash_Int::operator+=(string xs)
{
    int x;
    x = atoi(xs.c_str());

    int ok = 0, st = 1,v1,v2;

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

    L.push_back(x);
    int *aux;
    aux =&(L.back());

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

                h2[v2]= aux;
                viz2 [v2] = true;
                return true;
            }
            else
                if(viz2[v2]&&*h2[v2]==x)return true;
                    else
                    {
                        st = 1;
                        if( ok < 0)
                            {
                                int *auxx;
                                auxx = h2[v2];
                                h2[v2] = aux;
                                aux = auxx;
                                x = *aux;
                                v1 = F1->Hash(x);
                                v2 = F2->Hash(x);

                            }
                    }
        }
        ok--;
    }
    L.erase(L.begin(),L.end());
    return false;
}
void Cuckoo_Hash_Int::operator-=(string xs)
{
    int v1,v2,x;
    x = atoi(xs.c_str());
    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;
}
bool Cuckoo_Hash_Int::operator==(string sx)
{
     int x;
     x = atoi(sx.c_str());
     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;
}
class Cuckoo_Hash_UnInt:public Cuckoo_Hash
{
    list <unsigned int> L;
 public:
     bool operator+=(string);
     void operator-=(string);
     bool operator==(string);
     Cuckoo_Hash_UnInt(unsigned int s):Cuckoo_Hash(s){};
};
bool Cuckoo_Hash_UnInt::operator+=(string xs)
{
    unsigned int x;
    x = atoi(xs.c_str());

    int ok = 0, st = 1,v1,v2;

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

    L.push_back(x);
    int *aux;
    aux =(int*)&(L.back());

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

                h2[v2]= aux;
                viz2 [v2] = true;
                return true;
            }
            else
                if(viz2[v2]&&*(unsigned int*)h2[v2]==x)return true;
                    else
                    {
                        st = 1;
                        if( ok < 0)
                            {
                                int *auxx;
                                auxx = h2[v2];
                                h2[v2] = aux;
                                aux = auxx;
                                x = *(unsigned int*)aux;
                                v1 = F1->Hash(x);
                                v2 = F2->Hash(x);

                            }
                    }
        }
        ok--;
    }
    L.erase(L.begin(),L.end());
    return false;
}
void Cuckoo_Hash_UnInt::operator-=(string xs)
{
    int v1,v2;
    unsigned int x;
    x = atoi(xs.c_str());
    v1 = F1->Hash(x);
    v2 = F2->Hash(x);

    if(viz1[v1] && *(unsigned int*)h1[v1] == x) viz1[v1]=false;

        else if(viz2[v2] && *(unsigned int*)h2[v2] == x ) viz2[v2] = false;
}
bool Cuckoo_Hash_UnInt::operator==(string sx)
{
     unsigned int x;
     x = atoi(sx.c_str());
     int v1 = F1->Hash(x);
     int v2 = F2->Hash(x);
     if(viz1[v1] && *(unsigned int*)h1 [v1] == x) return true;
     if(viz2[v2] && *(unsigned int*)h2 [v2] == x ) return true;

    return false;
}

int main()
{
    int x;
    //cout<<"Alegeti tipul de date cu care veti lucra tastand:\n";
    //cout<<"1 = int\n2 = float\n3 = double\n4 = char\n5 = string\n6 = unsigned int ";
    x=6;
    srand (time(NULL));
    Cuckoo_Hash *H;
    switch(x)
    {case 1:H = new Cuckoo_Hash_Int(1000000);break;
     case 5:H = new Cuckoo_Hash(1000000);break;
     case 6:H = new Cuckoo_Hash_UnInt(550000);break;
    }
    H->Citeste();
    return 0;

}