// 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 FREE 0
#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,p,m;
public:
	bool generate(int prim,int h_size); // genereaza valorile a si b primind p si m
	int evaluate(int x); // evalueaza functia in punctul intreg x
	int evaluate(float x); // evaluam pe floaturi functia de hash
	int evaluate(double x); // evaluam pe doubleuri functia de hash
	int evaluate(string x); // evaluam pe stringuri functia de hash
};

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

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

int hash_function::evaluate(float x){ //functia de hash este ((a*{x*mult_magic}+b*[x*mult_magic])%p)%m
	double value=x*MULT_MAGIC;
	long long hvalue; // intram pe long long
	hvalue=(long long)((long long)a*(int)(value-(int)value)+(long long)b*(int)value);
	hvalue%=p;
	hvalue%=m;
	return (int)hvalue;
}
int hash_function::evaluate(double x){ //functia de hash este ((a*{x*mult_magic}+b*[x*mult_magic])%p)%m
	double value=x*MULT_MAGIC;
	long long hvalue; // intram pe long long
	hvalue=(long long)((long long)a*(int)(value-(int)value)+(long long)b*(int)value);
	hvalue%=p;
	hvalue%=m;
	return (int)hvalue;
}

int hash_function::evaluate(string x){
	long long hvalue=1,bloc=0;
	int shift_amount=0,l=x.size();
	for(int i=0;i<l;++i){
		hvalue*=FNV;
		hvalue^=x[i];
		hvalue%=p;
	}
	hvalue=(long long)((long long)a*(long long)bloc+(long long)b*hvalue);
	hvalue%=p;
	hvalue%=m;
	return hvalue;
}


template <class T> 
class hash{
	int size; // dimensiunea hashului
	bool *avail; // spune daca pozitia h[x] e libera sau nu ( true daca e libera si false daca e ocupata )
	T *h; // vom aloca dinamic un vector h de dimensiune size
	int p; // p numar random folosit pentru functiile de hash
	hash_function h1,h2;
public:
	hash<T>(int hash_size);
	~hash();
	int find(T value);
	bool erase(T value);
	bool insert(T value); // returneaza 1 daca insereaza cu succes si 0 fara succes ceea ce implica refacerea hashului
};

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

template <class T>
hash<T>::~hash(){
	delete [] this->h; // sterg zona alocata dinamica in hash
	delete [] this->avail;
}


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

template <class T>
bool hash<T>::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){
		avail[location]=true;
		clear(h[location]);
		return true;
	}
	return false;
}		

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

void clear(int & x){x=0;}
void clear(float & x){x=0;}
void clear(double & x){x=0;}
void clear(string & x){x.erase();}

bool solve(){
	ifstream in("hashuri.in");
	ofstream out("hashuri.out");
	int operations,opcode;
	string value;
	bool ok=1;
	in>>operations;
	hash <string> H(operations);	// declaram hashul necesar pentru un numar dat de operatii
	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;
}