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