#include<iostream>
#include<fstream>
using namespace std;
class hash_base
{
    protected:
        int *H;
        int size;
    public:
        virtual int f(int ,int );
        void operator+(int );
        void operator-(int );
        int operator==(int );
        void hash(char[] , char[] );
};
void hash_base::hash(char i[],char o[])
{
    int n,op;
    int x;
    ifstream in(i);
    ofstream out(o);
    fill(H,H+size,0);
    in>>n;
    for(int i=0;i<n;i++)
    {
        in>>op>>x;
        if(op==1)
            *this+x;
        if(op==2) this-x;
        if(op==3) out<<(*this==x)<<"\n";
    }
    in.close();
    out.close();
}
void hash_base::operator+(int x)
{
    if(*this==x) return;
    int i=0,pos,sem=0;
    while(1)
    {
        pos=f(x,i);
        if(H[pos]==0)
            {
                H[pos]=x;
                return;
            }
        else
            i++;
    }
}
void hash_base::operator-(int x)
{
    int i=0,pos;
    while(1)
    {
        pos=f(x,i);
        if(H[pos]==x || H[pos]==0)
            {
                H[pos]=0;
                return;
            }
        else
            i++;
    }
}
int hash_base::operator==(int x)
{
    int i=0,pos;
    while(1)
    {
        pos=f(x,i);
        if(H[pos]==x)
            return 1;
        if(H[pos]==0)
            return 0;
        i++;
    }
}
class linear_hash:public hash_base
{
    public:
        linear_hash(int s)
        {
            size=s;
            H=new int[size];
        }
        ~linear_hash() {delete[] H;}
        int f(int x,int i)
        {
            return ((long long)x%1200000041+i)%size;
        }
};
class double_hash:public hash_base
{
    public:
        double_hash(int s)
        {
            size=s;
            H=new int[size];
        }
        ~double_hash() {delete[] H;}
        int f(int x,int i)
        {
            return ((long long)x%1200000041+i*((long long)x%666013))%size;
        }
};
int main()
{
    hash_base* HTab;
    cout<<"1.Linear Hashing\n2.Double Hashing\nAlegeti metoda:";
    int x;cin>>x;
    if(x==1)
    {HTab=new linear_hash(1000003);}
    else
    {HTab=new double_hash(1000003);}
    HTab->hash("hashuri.in","hashuri.out");
    return 0;
}