#include<iostream>
#include<fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
 
using namespace std;
 
/*class Functie
{
private:
    int a , b;
    int mod;
    int size;
public:
    Functie(int &);
    void generare_parametri();
    int functie(int&);
    int functie(unsigned int&);
    int functie(float&);
    int functie(double&);
    int functie(char&);
    int functie(string&);
};
  
Functie::Functie(int &n)
{   
    size = n;
    generare_parametri();
}
  
void Functie::generare_parametri()
{
    int pr[]={999983,999979,899981,900007,800011};
    a = rand() % size+10;
    b = rand() % size+10;
    mod = pr[rand () % 5];
}
  
int Functie::functie(char &val)
{
    int poz;
    poz = ((a + b*val ) % mod) % size;
    return poz;
}
  
int Functie::functie(int &val)
{
    int poz;
    poz=((a + b*val ) % mod) % size;
    return poz;
}
 
int Functie::functie(unsigned int &val)
{
    int poz;
    poz=((a + b*val ) % mod) % size;
    return poz;
}
  
int Functie::functie(float &val)
{
    int poz;
    while ((val - (int)val) != 0)
    {
        val *= 10;
        if (val > size)
        {
            val -= size;
        }
    }
    poz = (((long)a + (long)b*(long)val ) % (long)mod) % (long)size;
    return poz;
}
  
int Functie::functie(double &val)
{
    int poz;
    while ((val - (int)val) != 0)
    {
        val *= 10;
        if (val > size)
        {
            val -= size;
        }
    }
    poz = (((long)a + (long)b*(long)val ) % (long)mod) % (long)size;
    return poz;
}
  
int Functie::functie(string &val)
{
    int aux = 0;
    for (int i =0;i<val.size();i++)
        aux = (aux+a + b*val[i])%size; 
    return aux;
}


*/
















// Hash-ul de Basic_Hash
class Basic_Hash
{
protected:
    int *hash1;
    int *hash2;
    int size; 
	int mod1, mod2;
	int a1, a2, b1, b2;
 
public:
		
	Basic_Hash(int n);
	virtual ~Basic_Hash();
	
	void Initializare();
	void generare_parametri();
	
	virtual void Rezolvare();
	virtual int functia1(int);
	virtual int functia2(int);
	
    bool operator += (int);
    void operator -= (int);
    bool operator == (int);

 
};

Basic_Hash::Basic_Hash(int n)  
{
	size=n;
		
	srand(time(NULL));
	
	hash1 = new int[size];
	hash2 = new int[size];
}

Basic_Hash::~Basic_Hash()
{
    delete[] hash1;
    delete[] hash2;
}

void Basic_Hash::generare_parametri()
{
    int pr[]={999983,999979,899981,900007,800011};
    a1 = rand() % size+10;
    b2 = rand() % size+10;
	a2 = rand() % size+10;
    b1 = rand() % size+10;
    mod1 = pr[rand () % 5];
	mod2 = pr[rand () % 5];
}

bool Basic_Hash::operator+=(int val)
{
    int nr=0, poz1, poz2, aux;
     
    poz1 = functia1(val);
    poz2 = functia2(val);
     
    if( hash1[poz1]==val || hash2[poz2]==val )
        return true;
     
    if(hash1[poz1]==0)
    {
        hash1[poz1]=val;
        return true;
    }
    else
        if(hash2[poz2]==0)
        {
            hash2[poz2]=val;
            return true;
        }
        else
        {
            aux = val;
            val = hash1[poz1];
            hash1[poz1] = aux;
        }
     
    while(nr<30)
    {
        nr++;
         
        poz2 = functia2(val);
         
        if(hash2[poz2]==0)
        {
            hash2[poz2]=val;
            return true;
        }
        else
        {
            poz1 = functia1(hash2[poz2]);
            aux=hash2[poz2];
            hash2[poz2]=val;
            val=hash1[poz1];
            hash1[poz1]=aux;
        }
    }
     
    return false;
}

void Basic_Hash::operator-=(int val)
{
    int poz1, poz2;
     
    poz1 = functia1(val);
    poz2 = functia2(val);
     
    if( hash1[poz1] == val )
        hash1[poz1]=0;
         
    else
        if( hash2[poz2] == val )
            hash2[poz2] = 0;
}

bool Basic_Hash::operator==(int val)
{
    int poz1, poz2;
     
    poz1 = functia1(val);
    poz2 = functia2(val);
     
    if( ( hash1[poz1] == val ) || ( hash2[poz2] == val ) )
        return 1;
    else
        return 0;
}
	
void Basic_Hash::Initializare()
{
    fill(hash1,hash1+size,0);
    fill(hash2,hash2+size,0);
    generare_parametri();
}
 







// Cuckoo Hash pentru Stringuri
 
class Hash_String : public Basic_Hash
{
  
	string *v;																/////////////////???????????
 
    public:
 
    Hash_String(int size) : Basic_Hash(size)
	{
		v=new string[size+1];
	}
	
	void Rezolvare();
	int functia1(int);
	int functia2(int);
    
};

void Hash_String::Rezolvare()
{
	int n, op, i, ok=0;
 
    srand( time( NULL ) );
     
     
    while(ok==0)
    {
        Initializare();
         
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
         
        f>>n;
         
        ok=1;
     
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>v[i];
         
            if(op==1)
				ok = *this += i;
			else
				if(op==2)
					*this -= i;
			else
				g<<(*this==i)<<"\n"; 
        }
         
        f.close();
        g.close();
         
    }
}

int Hash_String::functia1(int val)
{
    int aux = 0;
    for (int i =0;i<v[val].size();i++)
        aux = (aux+a1 + b1*v[val][i])%size; 
    return aux;
}

int Hash_String::functia2(int val)
{
    int aux = 0;
    for (int i =0;i<v[val].size();i++)
        aux = (aux+a2 + b2*v[val][i])%size; 
    return aux;
}



int main()
{
     
    Basic_Hash *h;
     
 
    h = new Hash_String(1000000);
  
      
    h->Rezolvare ();
 
    return 0;
}