// Ion Vlad-Doru, Grupa 135, Facultatea de Matematica si Informatica
// Cuckoo Hashing, Programare Orientata pe Obiecte

#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <string> 

#define NA -1
#define FNV 16777619

using namespace std;

const int PRIM=2147483647; // numarul prim mare folosit la evaluarea functiilor de hash random
const double MULT_MAGIC=0.618034;

class hash_function{ // h(x)=((a*x+b)%p)%m unde a si b sunt random si a!=0
	int a,b,m;
public:
	bool generate(int prim,int h_size); // genereaza valorile a si b primind p si m
	int code(int x); // evalueaza functia in punctul intreg x
};


bool hash_function::generate(int prim,int h_size){
	m=h_size;
	a=(rand())%(m);
	while(a==0) // ne asiguram ca a e diferit de 0
		a=(rand())%(m);
	b=(rand())%(m);
	if(a!=0 && b<=m && a<=m)
		return true;
	return false;
}

int hash_function::code(int x){
	long long value;	// intram pe long long
	value=(long long)((long long)a*(long long)x+(long long)b);
	value%=PRIM;
	value%=m;
	return (int)value;
}


// INTERFATA


template <class T> // functia evaluate e trimisa de utilizator pentru fiecare tip de date. Pentru tipul de date int se poate omite acest parametru.
class hash_base{
protected:
	int size; // dimensiunea hashului
	T *h; // vom aloca dinamic un vector h de dimensiune size
	bool *avail; // spune daca pozitia h[x] e libera sau nu ( true daca e libera si false daca e ocupata )
	hash_function h1,h2;
public:
	hash_base(int); // constructorul clasei
	virtual ~hash_base()=0; // destructorul 
	virtual int find(T)=0;
	virtual bool erase(T)=0;
	virtual bool insert(T)=0; // returneaza 1 daca insereaza cu succes si 0 fara succes ceea ce implica refacerea hashului
};

template <class T> 
hash_base<T>::hash_base(int hash_size){
	size=hash_size*3;	// aloc de trei ori numarul maxim de elemente ce se vor gasi in hash in acelasi timp deoarece fiecare element are doua valori de hashing asociate
	h=new T[size];
	avail=new bool[size];
	for(int i=0;i<size;++i) // initializam tabelul cu FREE peste tot
		avail[i]=true;//marchez fiecare pozitie ca fiind libera
	h1.generate(PRIM,size); // generez functiile random
	h2.generate(PRIM,size);
}

template <class T> 
hash_base<T>::~hash_base(){
	delete [] h;
}


// CLASA HASH DOUBLE


template<class T,int (*evaluate)(T)>
class hash_double: public hash_base<T>{
public:
	hash_double(int); // constructorul clasei
	~hash_double();
	int find(T);
	bool erase(T);
	bool insert(T); // returneaza 1 daca insereaza cu succes si 0 fara succes ceea ce implica refacerea hashului
};

template<class T,int (*evaluate)(T)>
hash_double<T,evaluate>::hash_double(int hash_size=0) : hash_base<T>(hash_size){;}

template<class T,int (*evaluate)(T)>
hash_double<T,evaluate>::~hash_double(){
	delete [] this->avail;
	delete [] this->h;
}

template<class T,int (*evaluate)(T)>
int hash_double<T,evaluate>::find(T value){ // caut valoarea value in una din cele doua pozitii posibile;
	int i=0,hvalue;
	for(i=1;i<=this->size;++i){
		hvalue=(this->h1.code((*evaluate)(value))+i* (this->h2.code((*evaluate)(value))))%(this->size);
		if(this->h[hvalue]==value && this->avail[hvalue]==false){
			return hvalue;
		}
		if(this->avail[hvalue]==true){
			return NA;
		}
	}
	return NA;
}

template<class T,int (*evaluate)(T)>
bool hash_double<T,evaluate>::erase(T value){ // caut valoarea value in una din cele doua pozitii posibile;
	int i=0,hvalue;
	for(i=1;i<=this->size;++i){
		hvalue=(this->h1.code((*evaluate)(value))+i*(this->h2.code((*evaluate)(value))))%(this->size);
		if(this->h[hvalue]==value && this->avail[hvalue]==false){
			this->avail[hvalue]=true;
			return true;
		}
		if(this->avail[hvalue]==true){
			return false;
		}
	}
	return false;
}


template<class T,int (*evaluate)(T)>
bool hash_double<T,evaluate>::insert(T value){ // eliberez locatia ocupata de value daca exista si returnez 1 daca eliberez si 0 altfel
	int i=0,hvalue;
	for(i=1;i<=this->size;++i){
		hvalue=(this->h1.code((*evaluate)(value))+i*(this->h2.code((*evaluate)(value))))%(this->size);
		if(this->avail[hvalue]==true){
			this->h[hvalue]=value;
			this->avail[hvalue]=false;
			return true;
		}
	}
	return false;
}		


// CLASA HASH CUCKOO

template<class T,int (*evaluate)(T)>
class hash_cuckoo: public hash_base<T>{
public:
	hash_cuckoo(int);
	~hash_cuckoo(); // destructorul 
	int find(T);
	bool erase(T);
	bool insert(T); // returneaza 1 daca insereaza cu succes si 0 fara succes ceea ce implica refacerea hashului
};

template<class T,int (*evaluate)(T)>
hash_cuckoo<T,evaluate>::hash_cuckoo(int hash_size=0) : hash_base<T>(hash_size){;}

template<class T,int (*evaluate)(T)>
hash_cuckoo<T,evaluate>::~hash_cuckoo(){
	delete [] this->avail;
	delete [] this->h;
}


template<class T,int (*evaluate)(T)>
int hash_cuckoo<T,evaluate>::find(T value){ // caut valoarea value in una din cele doua pozitii posibile;
	int location1=this->h1.code((*evaluate)(value)),location2=this->h2.code((*evaluate)(value));
	if(this->h[location1]==value && !this->avail[location1])
		return location1;
	if(this->h[location2]==value && !this->avail[location2])
		return location2;
	return NA;
}

template<class T,int (*evaluate)(T)>
bool hash_cuckoo<T,evaluate>::erase(T value){ // eliberez locatia ocupata de value daca exista si returnez 1 daca eliberez si 0 altfel
	int location=find(value);
	if(location!=NA){
		this->avail[location]=true;
		return true;
	}
	return false;
}		

template<class T,int (*evaluate)(T)>
bool hash_cuckoo<T,evaluate>::insert(T value){ // inserez valuarea value in tabel
	int location1,location2,explorated=0,upper_bound=(int)log((double)this->size);
	T aux,ant=value;
	location1=this->h1.code((*evaluate)(value)); // location1=h1(value)
	if(find(value)!=NA) // daca e deja inserat atunci iesim din metoda
		return true;
	if(this->avail[location1]){ // daca prima locatie e libera il inseram in hash
		this->h[location1]=value;
		this->avail[location1]=false;
		return true;
	}
	else{ //altfel scoatem ce se afla in hash pe prima locatie si punem elementul curent pe prima sa locatie
		aux=this->h[location1];
		this->h[location1]=value;
		this->avail[location1]=false;
		explorated++;
	}
	while(explorated<=upper_bound){ // cat timp am scos mai putin de log(hash size) elemente executam
		location1=this->h1.code((*evaluate)(aux));//calculam cele 2 pozitii posibile si ne uitam la ce diferita de pozitia de pe care elementul a fost scos
		location2=this->h2.code((*evaluate)(aux));
		if(this->h[location2]==ant){ // elementul a fost scos de pe pozita data de h2 si il inseram pe pozitia data de h1
			if(this->avail[location1]){ // daca aceasta a doua pozitie e libera inseram elementul
				this->h[location1]=aux;
				this->avail[location1]=false;
				return true;
			}
			else{ // altfel scoatem elementul de pe pozitia h1 si inseram elementul nostru
				ant=aux;
				aux=this->h[location1];
				this->h[location1]=ant;
			}
		}
		else{ // elementul a fost scos de pe pozitia data de h1
			if(this->avail[location2]){ //cazul se rezolva analog cu primul
				this->h[location2]=aux;
				this->avail[location2]=false;
				return true;
			}
			else{
				ant=aux;
				aux=this->h[location2];
				this->h[location2]=ant;
			}
		}
		explorated++; // crestem numarul de elemente explorate
	}
	return false;
}
	
bool solve();	
	
int main(){
	while(!solve()); // daca e nevoie de rehashing refacem hashul
	return 0;
}

int evaluate_float(float x){ //functia de hash este ((a*{x*mult_magic}+b*[x*mult_magic])%p)%m
	double value=x*MULT_MAGIC;
	return (int)value;
}
int evaluate_double(double x){ //functia de hash este ((a*{x*mult_magic}+b*[x*mult_magic])%p)%m
	double value=x*MULT_MAGIC;
	return (int)value;
}

int evaluate_string(string x){ // FNV hashing for strings 
	long long hvalue=1;
	int l=x.size();
	for(int i=0;i<l;++i){
		hvalue*=FNV;
		hvalue^=x[i];
		hvalue%=PRIM;
	}
	return hvalue;
}

int evaluate_int(int x){
	return x;
}

bool solve(){
	ifstream in("hashuri.in");
	ofstream out("hashuri.out");
	int operations,opcode;
	int value;
	bool ok=1;
	in>>operations;
	hash_base<int> *H;	// declaram interfata si tipul de date cu care vom lucra
	H=new hash_cuckoo<int,evaluate_int>(operations); // Alocam hashul in functie de tipul de date cu care vom lucra si functia care va converti tipul la un int
	for(int i=1;i<=operations;++i){
		in>>opcode>>value;
		if(opcode==1){
			ok=(*H).insert(value);
			if(!ok){
				cout<<"E nevoie de rehashing";
				in.close();
				out.close();
				return false;
			}
			continue;
		}				
		if(opcode==2){
			(*H).erase(value);
			continue;
		}
		if(opcode==3){
			if((*H).find(value)==NA)
				out<<"0\n";
			else
				out<<"1\n";
		}
	}
	return true;
}