#define DM 21
#include <cstring>
#include <fstream>
using namespace std;	
 
ifstream fi ("trie.in");
ofstream fo ("trie_alt.out");
char s[DM];//cuvant
int o;//tipul de operatie	
 
struct trie	
{
	int cnt, nr;//nr de cuvinte ce se termina in nod, nr de fii
	trie *fiu[27];//fiii nodului
	trie()//build
	{
		cnt = nr = 0;//0 cuvinte terminate
		memset(fiu, 0, sizeof(fiu));//niciun fiu
	}	
};	
 
trie *root = new trie();	
 
//pt a adauga un cuvant ii bag toate caracterele in noduri
void add(char *c, trie *nod)//adaug un nod	
{
	if (*c == 0)//daca am ajuns la capatul cuvantului, crestem cnt
	{
		++nod->cnt;
		return;
	}
	int delta = *c - 'a';//pozitia caracterului in vectorul de fii
	if (nod->fiu[delta] == 0)//daca nu exista fiu, il construim
	{
		nod->fiu[delta] = new trie();
		++nod->nr;
	}
	add(c + 1, nod->fiu[delta]);//urmatorul caracter	
}	
 
bool del(trie *nod, char *c)//sterg un cuvant	
{
	if (*c == 0)//scoatem cuvantul
	{
		--nod->cnt;//scadem contorul nodului
		if (nod->nr == 0 && nod->cnt == 0 && nod != root)
		{
			delete nod;//ce face delete?
			return 1;
		}
		return 0;
	}
	int delta = *c - 'a';
	if (del(nod->fiu[delta], c + 1))
	{
		--nod->nr;
		nod->fiu[delta] = 0;
		if (nod->nr == 0 && nod->cnt == 0 && nod != root)
		{
			delete nod;
			return 1;
		}
	}
	return 0;	
}	
 
//pt a cauta un cuvant ii caut toate caracterele pe rand
int fnd(trie *nod, char *c)//interogheaza un nod 	
{
	if (*c == 0)//am terminat caracterele cuvantului de cautat
		return nod->cnt;//cate cuvinte se termina in nodul curent
	int delta = *c - 'a';
	if (nod->fiu[delta] == 0)//*c != 0 => mai avem nevoie de caractere, nod->fiu[delta] == 0 => nu mai avem caracetere dupa nod
		return 0;
	return fnd(nod->fiu[delta], c + 1);	
}	
 
int pfx(trie *nod, char *a)	
{
	if (*a == 0)
		return 0;
	int delta = *a - 'a';
	if (nod->fiu[delta] == 0)
		return 0;
	return 1 + pfx(nod->fiu[delta], a + 1);	
}

void parcurge(trie * crt) {
	fo << "nrSons : " << crt->nr << "  -  ending : " << crt->cnt << '\n';
	for (int i = 0; i < 27; ++i)
		if (crt->fiu[i] != 0) {
			char aux = 'a';
			aux += i;
			fo << "entering " << aux << '\n';
			parcurge(crt->fiu[i]);
		}
}	
 
int main()	
{
	while (fi >> o)//cat timp pot lua comenzi
	{
		fi >> s;//citesc cuvantul
		if (o == 0)
			add(s, root);
		if (o == 1) {
			del(root, s);
			parcurge(root);
		}
		if (o == 2)
			fo << fnd(root, s) << '\n';
		if (o == 3)
			fo << pfx(root, s) << '\n';
	}
	// parcurge(root);
}