// 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
{
protected:
    list <string> L;
    int **h1, **h2;
    int size_h;
    bool *viz1,*viz2;
    Hash_Func *F1,*F2;

public:
    bool operator+=(string);
    void operator-=(string);
    bool operator==(string);
    void Citeste();
    Cuckoo_Hash(unsigned int);
    ~Cuckoo_Hash();
    virtual void CalcV1V2(int&, int&v, string);
    virtual bool Egal(int*,string);

};
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;
   L.erase(L.begin(),L.end());
}
void Cuckoo_Hash::CalcV1V2(int &v1,int &v2, string x)
{
    v1=F1->Hash(x);
    v2=F2->Hash(x);
}
bool Cuckoo_Hash::Egal(int *p,string x)
{
    if(*(string*)p == x)return true;
    return false;
}
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;

    CalcV1V2(v1,v2,x);
    int *aux;
    L.push_back(x);
    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] && Egal(h1[v1],x))return true;
                else
                {
                    st = -1;
                    if( ok < 0)
                    {
                        int *auxx;
                        auxx = aux;
                        aux =  h1 [v1];
                        h1 [v1] = auxx;
                        x = *(string*)aux;
                        CalcV1V2(v1,v2,x);
                    }
                }
        }
        if( st == -1)
        {
            if(!viz2[v2])
            {

                h2[v2]= aux;
                viz2 [v2] = true;
                return true;
            }
            else
                if( viz2[v2] && Egal(h2[v2], x) )return true;
                    else
                    {
                        st = 1;
                        if( ok < 0)
                            {
                                int *auxx;
                                auxx = h2[v2];
                                h2[v2] = aux;
                                aux = auxx;
                                x = *(string*)aux;
                                CalcV1V2(v1,v2,x);
                            }
                    }
        }
        ok--;
    }
    L.erase(L.begin(),L.end());
    return false;
}
void Cuckoo_Hash::operator-=(string x)
{
    int v1,v2;
    CalcV1V2(v1,v2,x);
    if(viz1[v1] && Egal(h1[v1],x)) viz1[v1]=false;

        else if(viz2[v2] && Egal(h2[v2],x)) viz2[v2] = false;
}
bool Cuckoo_Hash::operator==(string x)
{
    int v1,v2;
    CalcV1V2(v1,v2,x);

    if(viz1[v1] && Egal(h1[v1],x)) return true;
    if(viz2[v2] && Egal(h2[v2],x)) return true;

    return false;
}
//Clasa derivata de Cuckoo_Hash pentru Int
class Cuckoo_Hash_Int:public Cuckoo_Hash
{

    public:
    void CalcV1V2(int&, int&v, string);
    bool Egal(int*,string);
    Cuckoo_Hash_Int(unsigned int s):Cuckoo_Hash(s){};
};
void Cuckoo_Hash_Int::CalcV1V2(int &v1,int &v2, string xs)
{
    int x;
    x=atoi(xs.c_str());
    v1=F1->Hash(x);
    v2=F2->Hash(x);
}
bool Cuckoo_Hash_Int::Egal(int *p,string xs)
{
    int x,y;
    x = atoi(xs.c_str());
    xs = *(string*)p;
    y = atoi(xs.c_str());
    if(y == x)return true;
    return false;
}
//Clasa derivata de Cuckoo_Hash pentru Unsigned Int

class Cuckoo_Hash_UnInt:public Cuckoo_Hash
{

    public:
    void CalcV1V2(int&, int&v, string);
    bool Egal(int*,string);
    Cuckoo_Hash_UnInt(unsigned int s):Cuckoo_Hash(s){};
};
void Cuckoo_Hash_UnInt::CalcV1V2(int &v1,int &v2, string xs)
{
    unsigned int x;
    x=atoi(xs.c_str());
    v1=F1->Hash(x);
    v2=F2->Hash(x);
}
bool Cuckoo_Hash_UnInt::Egal(int *p,string xs)
{
    unsigned int x,y;
    x = atoi(xs.c_str());
    xs = *(string*)p;
    y = atoi(xs.c_str());
    if(y == x)return true;
    return false;
}
// Clasa derivata de Cuckoo_Hash pentru Double

class Cuckoo_Hash_Double:public Cuckoo_Hash
{

    public:
    void CalcV1V2(int&, int&v, string);
    bool Egal(int*,string);
    Cuckoo_Hash_Double(unsigned int s):Cuckoo_Hash(s){};
};
void Cuckoo_Hash_Double::CalcV1V2(int &v1,int &v2, string xs)
{
    double x;
    x=atof(xs.c_str());
    v1=F1->Hash(x);
    v2=F2->Hash(x);
}
bool Cuckoo_Hash_Double::Egal(int *p,string xs)
{
    double x,y;
    x = atof(xs.c_str());
    xs = *(string*)p;
    y = atof(xs.c_str());
    if(y == x)return true;
    return false;
}

int main()
{
    int x,nr;
    /*cout<<"Alegeti tipul de date cu care veti lucra\n";
    cout<<"1 = int\n2 = unsigned int\n3 = double\n4 = string\n";
    cin>>x;
    cout<<"Dati numarul maxim de operatii ce se pot efectua:\n";
    cin>>nr;*/
    x=2;nr=1000000;
    srand (time(NULL));
    nr = nr/2 + 40000;
    Cuckoo_Hash *H;
    switch(x)
    {
        case 1:H = new Cuckoo_Hash_Int(nr);break;
        case 2:H = new Cuckoo_Hash_UnInt(nr);break;
        case 3:H = new Cuckoo_Hash_Double(nr);break;
        case 4:H = new Cuckoo_Hash(nr);break;
    }
    H->Citeste();
    return 0;

}