/******* Berceanu Cristian 134 ******/
/* Cuckoo Hash cu functii virtuale */ 
#include <stdio.h>
#include <vector>
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <cstdio>
using namespace std;

class BaseHash
{
protected:
	unsigned int *hash1, *hash2;
	unsigned int size; 
	unsigned int mod1, mod2;
	unsigned int a1, a2, b1, b2;

public:
 
	BaseHash(unsigned int n);
	virtual ~BaseHash();
	void init();
	void params();
	virtual void solve()=0;
	virtual unsigned int hashFunction1(unsigned int &)=0;
	virtual unsigned int hashFunction2(unsigned int &)=0;
	virtual bool compare(unsigned int, unsigned int)=0;
	bool operator += (unsigned int);
	void operator -= (unsigned int);
	bool operator == (unsigned int);
 
};
 
BaseHash::BaseHash(unsigned int n)  
{
	size=n;
	hash1 = new unsigned int[size];
	hash2 = new unsigned int[size];
}
 
BaseHash::~BaseHash()
{
	delete[] hash1;
	delete[] hash2;
}
 
void BaseHash::params()
{
	unsigned int pr[]={999983,999979,899981,900007,800011};
	a1 = rand()%size;
	a2 = rand()%size;
	b1 = rand()%size;
	b2 = rand()%size;
	mod1 = pr[rand ()%5];
	mod2 = pr[rand ()%5];
}
 
bool BaseHash::operator+=(unsigned int val)
{
	unsigned int nr=0, poz1, poz2, aux;
	poz1 = hashFunction1(val);
	poz2 = hashFunction2(val);
	if((compare(hash1[poz1],val)) || (compare(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 = hashFunction2(val);  
			if(hash2[poz2]==0)
			{
				hash2[poz2]=val;
				return true;
			}
			else
			{
				poz1 = hashFunction1(hash2[poz2]);
				aux=hash2[poz2];
				hash2[poz2]=val;
				val=hash1[poz1];
				hash1[poz1]=aux;
			}
		}
		return false;
}
 
void BaseHash::operator-=(unsigned int val)
{
	unsigned int poz1, poz2;
	poz1 = hashFunction1(val);
	poz2 = hashFunction2(val);
	if(compare(hash1[poz1],val))
		hash1[poz1]=0;
	else
		if(compare(hash2[poz2],val))
			hash2[poz2] = 0;
	}
 
bool BaseHash::operator==(unsigned int val)
{
	unsigned int poz1, poz2;
	poz1 = hashFunction1(val);
	poz2 = hashFunction2(val);
	if(compare(hash1[poz1], val) || compare(hash2[poz2], val))
		return 1;
	else
		return 0;
}
 
void BaseHash::init()
{
	fill(hash1,hash1+size,0);
	fill(hash2,hash2+size,0);
	params();
}
   
class StringHash:public BaseHash
{
	string *v;
public:
	StringHash(unsigned int size):BaseHash(size)
	{
		v = new string[size+1];
	}
	~StringHash(){delete[] v;}
	void solve();
	unsigned int hashFunction1(unsigned int &);
	unsigned int hashFunction2(unsigned int &);
	bool compare(unsigned int, unsigned int);
 
};

void StringHash::solve()
{
	unsigned int n, op, i, ok=0;
	while(ok==0)
	{
		init();  
		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();
		}
}
 
unsigned int StringHash::hashFunction1(unsigned int &val)
{
	unsigned int aux = 0;
	for (unsigned int i = 0;i < v[val].size(); i++)
		aux = (aux+a1 + b1*v[val][i])%size; 
	return aux;
}
 
unsigned int StringHash::hashFunction2(unsigned int &val)
{
	unsigned int aux = 0;
	for (unsigned int i = 0;i < v[val].size(); i++)
		aux = (aux+a2 + b2*v[val][i])%size; 
	return aux;
}
 
bool StringHash::compare(unsigned int x, unsigned int y)
{
	if(v[x] == v[y])
		return 1;
	else
		return 0;
}

class IntHash:public BaseHash
{
   
	int *v;  
public:
	IntHash(unsigned int size):BaseHash(size)
	{
		v = new int[size+1];
	}
	~IntHash(){ delete[] v;}
	void solve();
	unsigned int hashFunction1(unsigned int &);
	unsigned int hashFunction2(unsigned int &);
	bool compare(unsigned int, unsigned int);
};
void IntHash::solve()
{
unsigned int n, op, i, ok=0;
while(ok==0)
{
	init();
	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();
	}
}

unsigned int IntHash::hashFunction1(unsigned int &val)
{
	unsigned int poz; 
	poz=((a1 + b1*v[val])%mod1)%size;
	return poz;
}
 
unsigned int IntHash::hashFunction2(unsigned int &val)
{
	unsigned int poz;
	poz=((a2 + b2*v[val])%mod2)%size;
	return poz;
}
 
bool IntHash::compare(unsigned int x, unsigned int y)
{
	if(v[x]==v[y])
		return 1;
	else
		return 0;
}
 

class DoubleHash:public BaseHash
{
	double *v; 
public:
  
	DoubleHash(unsigned int size):BaseHash(size)
	{
		v = new double[size+1];
	}
	~DoubleHash(){ delete[] v;}
	void solve();
	unsigned int hashFunction1(unsigned int &);
	unsigned int hashFunction2(unsigned int &);
	bool compare(unsigned int, unsigned int);
 
};
 
void DoubleHash::solve()
{
	unsigned int n, op, i, ok=0;
  
	while(ok==0)
	{
		init();
		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();
		}
}
 
unsigned int DoubleHash::hashFunction1(unsigned int &val)
{
	unsigned int poz;
	while ((v[val]- int(v[val])) != 0)
	{
		v[val] *= 10;
		if (v[val] > size)
		{
			v[val] -= size;
		}
	}
	poz = (((unsigned int)a1 + (unsigned int)b1*(unsigned int)v[val])%(unsigned int)mod1)%(unsigned int)size;
	return poz;
}
 
unsigned int DoubleHash::hashFunction2(unsigned int &val)
{
	int poz;
	while ((v[val] - int(v[val])) != 0)
	{
		v[val] *= 10;
		if (v[val] > size)
		{
			v[val] -= size;
		}
	}
	poz = (((unsigned int)a2 + (unsigned int)b2*(unsigned int)v[val])%(unsigned int)mod2)%(unsigned int)size;
	return poz;
}
 
bool DoubleHash::compare(unsigned int x, unsigned int y)
{
	if(v[x]==v[y])
		return 1;
	else
		return 0;
}
 
class FloatHash:public BaseHash
{  
	float *v;
  
public:
  
	FloatHash(unsigned int size):BaseHash(size)
	{
		v = new float[size+1];
	}
	~FloatHash(){ delete[] v;}
	void solve();
	unsigned int hashFunction1(unsigned int &);
	unsigned int hashFunction2(unsigned int &);
	bool compare(unsigned int, unsigned int);
 
};
 
void FloatHash::solve()
{
	unsigned int n, op, i, ok=0;
	while(ok==0)
	{
		init();
		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();
		}
}
 
 
unsigned int FloatHash::hashFunction1(unsigned int &val)
{
unsigned int poz;
 
while ((v[val] - int(v[val])) != 0)
{
	v[val] *= 10;
	if (v[val] > size)
	{
		v[val] -= size;
	}
}
poz = (((unsigned int)a1 + (unsigned int)b1*(unsigned int)v[val])%(unsigned int)mod1)%(unsigned int)size;
return poz;
}
 
unsigned int FloatHash::hashFunction2(unsigned int &val)
{
int poz;
 
while ((v[val] - int(v[val])) != 0)
{
	v[val] *= 10;
	if (v[val] > size)
	{
		v[val] -= size;
	}
}
poz = (((unsigned int)a2 + (unsigned int)b2*(unsigned int)v[val])%(unsigned int)mod2)%(unsigned int)size;
return poz;
}
 
bool FloatHash::compare(unsigned int x, unsigned int y)
{
if(v[x]==v[y])
	return 1;
else
	return 0;
}
class UnsignedIntHash:public BaseHash
{  
	unsigned int *v; 
public:
  
	UnsignedIntHash(unsigned int size):BaseHash(size)
	{
		v = new unsigned int[size+1];
	}
	~UnsignedIntHash(){ delete[] v;}
	void solve();
	unsigned int hashFunction1(unsigned int &);
	unsigned int hashFunction2(unsigned int &);
	bool compare(unsigned int, unsigned int);
 
};
 
void UnsignedIntHash::solve()
{
	unsigned int n, op, i, ok=0;  
	while(ok==0)
	{
		init();
		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();  
		}
}
 
unsigned int UnsignedIntHash::hashFunction1(unsigned int &val)
{
	unsigned int poz;
	poz=((a1 + b1*v[val])%mod1)%size;
	return poz;
}
 
unsigned int UnsignedIntHash::hashFunction2(unsigned int &val)
{
	unsigned int poz;
	poz=((a2 + b2*v[val])%mod2)%size;
	return poz;
}
 
bool UnsignedIntHash::compare(unsigned int x, unsigned int y)
{
	if(v[x]==v[y])
		return 1;
	else
		return 0;
}
 
 
int main()
{
	int x=2;
	srand(time(NULL));
	BaseHash *h;
	while(x<1||x>5)
	{
		cout<<"introduceti o valoare intre 1 si 5: ";
		cin>>x;
	}
	if(x==1)
		h = new UnsignedIntHash(1000000);
	else
		if(x==2)
			h = new IntHash(1000000);
		else
			if(x==3)
				h = new FloatHash(1000000);
			else
				if(x==4)
					h = new DoubleHash(1000000);
				else
					h = new StringHash(1000000);
				h->solve();
  
return 0;
}