#include <fstream>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

class hash_functions
{
private:
    int a,b;
    int MOD;
    unsigned int hash_size;
public :
    hash_functions(int);//constructorul care va primi ca parametru dimensiunea tabelelor si va genera
    void Generate();
    int Hash(int&);
    int Hash(double&);
    int Hash(float&);
    int Hash(unsigned int&);
    int Hash(char&);
    int Hash(string&);
};



void hash_functions::Generate()
{
    a= rand() % 666013 +2;
    b= rand() % 10000003 + 2;
    MOD= 4865447;
}
hash_functions::hash_functions(int n)
{
    hash_size=n;
    Generate();
}

int hash_functions:: Hash( int&x)
{
    return (  ( a*x + b ) % MOD )% hash_size;
}

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

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

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

int hash_functions :: Hash( char &x)
{
    return ( ( (int)(a*x)+b)%MOD) % hash_size;

}

int hash_functions :: Hash( string&x)
{
    int value=0;
    for (int contor=0;contor<x.size();contor++)
            value = ( (value *256)+ (int)x[contor]) % MOD;
    return abs( a*value + b)%hash_size;
}
//clasa base va avea 2 clase mostenite:
// una Cuckoo_Hashing si una Chaining

template <class Type>
class Base
{

public:
    virtual bool operator+=(Type&)=0;
    virtual void operator-=(Type&)=0;
    virtual bool operator==(Type&)=0;
};

template<class Type>
class Cuckoo_Hash : public Base<Type>
{
private:
 unsigned
 int nr;
 int hash_size;
    Type *table1,*table2;
    Type *values;
    bool *ope,*viz1,*viz2;
    hash_functions *f1,*f2;
public:
    Cuckoo_Hash(unsigned int);
    ~Cuckoo_Hash();
    bool operator+=(Type&);
    void operator-=(Type&);
    bool operator==(Type&);
    void Rehash();
};

template<class Type>
Cuckoo_Hash<Type> :: Cuckoo_Hash(unsigned int n)
{   nr=0;
    hash_size=n;
    f1=new hash_functions(hash_size);
    f2=new hash_functions(hash_size);
    table1=new Type[hash_size];
    table2=new Type[hash_size];
    values=new Type[hash_size];
    ope   =new bool[hash_size];
    viz1  =new bool[hash_size];
    viz2  =new bool[hash_size];
    fill(viz1,viz1+hash_size,false);
    fill(viz2,viz2+hash_size,false);
}

template<class Type>
Cuckoo_Hash<Type> :: ~Cuckoo_Hash()
{
    delete []table1;
    delete []table2;
    delete []ope;
    delete [] values;
    delete [] viz1;
    delete [] viz2;
    delete f1;
    delete f2;
}

template <class Type>
bool Cuckoo_Hash<Type> :: operator==(Type &x)//interogare
{
    int h1=f1->Hash(x);
    int h2=f2->Hash(x);
    if ( viz1[h1]==true && table1[h1]==x) return 1;
    if ( viz2[h2]==true && table2[h2]==x) return 1;
    return 0;
}

template <class Type>
void Cuckoo_Hash<Type> :: operator-=(Type &x)//stergere
{
    int h1=f1->Hash(x);
    int h2=f2->Hash(x);
    ope[nr]=false;
    ope[nr++]=x;
    if (viz1[h1]==true && table1[h1]==x)
        viz1[h1]=false;
    if (viz2[h2]==true && table2[h2]==x)
        viz2[h2]=false;
}

template <class Type>
bool Cuckoo_Hash<Type> :: operator+=(Type &x)//adaugare;
{

    int h1=f1->Hash(x);
    int h2=f2->Hash(x);
    ope[nr]=true;
    values[nr++]=x;
    if ( ((*this)==x)==false)
    {
        for (int i=1;i<=30;i++)
            {
                if (viz1[h1]==false)
                 {
                    table1[h1]=x;
                    viz1[h1]=true;

                    return true;
                 }
                 if (viz2[h2]==false)
                 {
                     table2[h2]=x;
                     viz2[h2]=true;
                     return true;
                 }
                 Type aux=table2[h2];
                 table2[h2]=x;
                 x=aux;
            }
        Rehash();
    }
}
template <class Type>
void Cuckoo_Hash<Type>:: Rehash()
{
    fill(viz1,viz1+hash_size,false);
    fill(viz2,viz2+hash_size,false);
    f1->Generate();
    f2->Generate();
    for (int i=0;i<nr;i++)
        if (ope[i]==true) *this+=values[i];
                     else *this-=values[i];
}


template <class Type>
class Chaining_Hash:public Base<Type>
{
private:
int hash_size;
    vector<Type> *table;
    hash_functions *f;
public:
    Chaining_Hash(unsigned int);
    ~Chaining_Hash();
    bool operator+=(Type&);
    void operator-=(Type&);
   bool operator==(Type&);

};
template <class Type>
Chaining_Hash< Type>::Chaining_Hash(unsigned int n)
{
    hash_size=n;

    f=new hash_functions(hash_size);
    table=new vector<Type>[hash_size];

}
template <class Type>
Chaining_Hash< Type> :: ~Chaining_Hash()
{
    delete[] table;
    delete f;
}
template <class Type>
bool Chaining_Hash<Type> ::operator==(Type &x)
{

    int h=f->Hash(x);

    for (int i=0;i<table[h].size();i++)
        if (table[h][i]==x) return 1;
    return 0;
}
template <class Type>
void Chaining_Hash<Type> ::operator-=(Type &x)
{

    int h=f->Hash(x);
    Type b;
    int a;

    for (int i=0;i<table[h].size();i++)
        if (table[h][i]==x)
            {
                table[h][i]=table[h][table[h].size()-1];
                table[h].pop_back();
                return ;
            }
}
template <class Type>
bool Chaining_Hash<Type> :: operator+=(Type &x)
{
    int h=f->Hash(x);
    for (int i=0;i<table[h].size();i++)
        if (table[h][i]==x) return false;//se gaseste in hash
    table[h].push_back(x);
    return true;
}
int main()
{   int x;
    unsigned int n,op,val;
    ifstream in("hashuri.in");
    ofstream out("hashuri.out");
  //  cout<<"Selectati metoda de hashing: pentru Cuckoo apasati 1 , iar pentru Chaining apasati 2";
  //  cin<<x;
    srand(time(NULL));
    Base<unsigned int> *H;

    x=2;
    switch(x)
    {
        case 1: H=new Cuckoo_Hash<unsigned int>(1000000); break;
        case 2: H=new Chaining_Hash<unsigned int> (1000000); break;
    }
    in>>n;
    for(int i=0;i<n;i++)
    {
        in>>op>>val;
        switch (op)
        {
            case 1: *H+=val;break;
            case 2: *H-=val; break;
            case 3:  out<<( *H==val)<<'\n';
                    break;
        }
    }
    in.close();
    out.close();
    return 0;
}