//Balcau Ionut, grupa 134 - dublu hash cu template(Cuckoo si chaining)

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <vector>

typedef unsigned int uint;
 
using namespace std;
 
template<class type>
class baseHash{
  
public:
	virtual void init()=0;
	virtual bool operator==(type &)=0;
	virtual bool operator+=(type &)=0;
	virtual void operator-=(type &)=0;
	bool solveHashuri();
  
};
template<class type>
bool baseHash<type>::solveHashuri(){
	uint n, op, i, ok=0;
	type x;
	 
	srand(time(NULL));
	 
	
	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>>x;
		 
			if(op==1)
				ok = *this += x;
			else
				if(op==2)
					*this -= x;
				else
					g<<(*this==x)<<"\n"; 
		}
		 
		f.close();
		g.close();
		 
	}
  
}


//----------------- Hash Function Class ------------
class hashFunction{
private:
	uint a , b;
	uint m;
	uint size;
public:
	hashFunction(uint &);
	void setParams();
	uint hf(char&);
	uint hf(string&);
	uint hf(int&);
	uint hf(uint&);
	uint hf(float&);
	uint hf(double&);
};

void hashFunction::setParams(){
	a = 800000 + rand()%200000;
	b = 800000 + rand()%200000;
	m = 800000 + rand()%200000;
}
  
hashFunction::hashFunction(uint &n){   
	size = n;
	setParams();
}
  
  
uint hashFunction::hf(char &x){
	uint pos;
	pos = ((a + b*x) % m) % size;
	return pos;
}
uint hashFunction::hf(uint &x){
	uint pos;
	pos=((a + b*x) % m) % size;
	return pos;
}
  
uint hashFunction::hf(int &x){
	uint pos;
	pos=((a + b*x) % m) % size;
	return pos;
}
 
uint hashFunction::hf(double &x){
	uint pos;
	while ((x - (int)x) != 0){
		x *= 10;
		if (x > size)
		{
			x -= size;
		}
	}
	pos = ((a + b*(uint)x) % m) % size;
	return pos;
}
  
uint hashFunction::hf(float &x){
	uint pos;
	while ((x - (int)x) != 0){
		x *= 10;
		if (x > size)
		{
			x -= size;
		}
	}
	pos = ((a + b*(uint)x) % m) % size;
	return pos;
}
  
  
uint hashFunction::hf(string &x){
	uint aux = 0;
	for (uint i =0;i<x.size();i++)
		aux = (aux+a + b*x[i])%size; 
	return aux;
}

//-------------- Chaining Hash ----------------
template<class type>
class chainHash:public baseHash<type>{
	uint size, nr;
	type *v;
	vector<uint> hash[666013];
	hashFunction *fh;
  
public:
	void init();
	chainHash(uint);
	~chainHash();
	bool operator==(type &);
	bool operator+=(type &);
	void operator-=(type &);
};

template<class type>
void chainHash<type>::init(){
	nr=0;
	
	fh->setParams();
}
  
template<class type>
chainHash<type>::chainHash(uint x){
	uint i;
	size = x;
	v=new type[size+1];
	fh = new hashFunction(size);
}
  
template<class type>
chainHash<type>::~chainHash(){
   delete[] v;
   delete fh;
}

template<class type>
bool chainHash<type>::operator==(type &x){
	 uint pos, i;
	 vector<uint>::iterator it;
	 pos = fh->hf(x);
  
	for(it=hash[pos].begin();it!=hash[pos].end();it++)
		if(v[*it]==x) 
			return true;
  
	return false;
}

template<class type>
bool chainHash<type>::operator+=(type &x){
	vector<uint>::iterator it;
	uint pos, i;
	pos= fh->hf(x);
	v[++nr]=x;
	
	for(it=hash[pos].begin();it!=hash[pos].end();it++)
		if(v[*it]==x) 
			return true;
		
	hash[pos].push_back(nr);
	return true;
}

template<class type>
void chainHash<type>::operator-=(type &x){
	uint pos, i;
	vector<uint>::iterator it;
	pos = fh->hf(x);
	
	for(it=hash[pos].begin();it!=hash[pos].end();it++)
		if(v[*it]==x) 
			break;

	if(it!=hash[pos].end()){
		*it=hash[pos].back();
		hash[pos].pop_back();
	}
}

  


// ----------------- Cuckoo Hash -------------------------
template<class type>
class cuckooHash:public baseHash<type>{
	uint size;
	bool *v1, *v2;
	type *hash1, *hash2;
	hashFunction *fh1, *fh2;
  
	public:
		void init();
		cuckooHash<type>(uint);
		~cuckooHash<type>();
		bool operator == (type &);
		bool operator += (type &);
		void operator -= (type &);
};
  
template<class type>
void cuckooHash<type>::init(){
	fill(v1,v1+size,0);
	fill(v2,v2+size,0);
	fh1->setParams();
	fh2->setParams();
}

template<class type>
cuckooHash<type>::cuckooHash(uint n){
	size = n;
	fh1 = new hashFunction(size); fh2 = new hashFunction(size);
	hash1 = new type[size]; hash2 = new type[size];
	v1 = new bool[size]; v2 = new bool[size];
}
  
template<class type>
cuckooHash<type>::~cuckooHash(){
	delete fh1; delete fh2;
	delete[] hash1; delete[] hash2;
	delete[] v1; delete[] v2;
}
 
template<class type>
bool cuckooHash<type>::operator==(type &x){
	uint p1, p2;
	 
	p1= fh1->hf(x);
	p2= fh2->hf(x);
	 
	if((hash1[p1] == x && v1[p1] == 1) || (hash2[p2] == x && v2[p2] == 1))
		return 1;
	else
		return 0;
}
 
template<class type>
bool cuckooHash<type>::operator+=(type &x){
	uint nr=0, p1, p2;
	type aux;
	 
	p1 = fh1->hf(x);
	p2 = fh2->hf(x);
	 
	if((hash1[p1]==x && v1[p1] ==1) || (hash2[p2]==x && v2[p2]==1))
		return 1;
	 
	if(v1[p1]==0){
		hash1[p1]=x;
		v1[p1]=1;
		return true;
	}
	else
		if(v2[p2]==0)
		{
			hash2[p2]=x;
			v2[p2]=1;
			return true;
		}
		else
		{
			aux = x;
			x = hash1[p1];
			hash1[p1] = aux;
		}
	 
	while(nr<20){
		nr++;
		 
		p2 = fh2->hf(x);
		 
		if(v2[p2]==0)
		{
			hash2[p2]=x;
			v2[p2]=1;
			return 1;
		}
		else
		{
			p1 = fh1->hf(hash2[p2]);
			aux=hash2[p2];
			hash2[p2]=x;
			x=hash1[p1];
			hash1[p1]=aux;
		}
	}
	 
	return false;
}

template<class type>
void cuckooHash<type>::operator-=(type &x){
	uint p1, p2;
	 
	p1 = fh1->hf(x);
	p2 = fh2->hf(x);
	 
	if((hash1[p1] == x) && v1[p1] == 1)
		v1[p1]=0;
		 
	else
		if(hash2[p2] == x && v2[p2] == 1)
			v2[p2] = 0;
}

  
  
int main(){
	
	
	baseHash <uint> *h;
	

	int x=1;	
	if(x==1)
		h = new chainHash<uint>(1000001);
	else
		h = new cuckooHash<uint>(1000001);
	h->solveHashuri ();
	return 0;
}