#include <stdio.h>
#include <string.h>
struct Trie
{
	int words,nr_fii;
	Trie * edges[26];
	
	Trie()
	{
		words = nr_fii = 0;
		memset(edges,0,sizeof(edges));
	}
};

Trie *T = new Trie;


int firstS(char *S)
{
	return *S - 'a';
}

void Add(Trie *nod, char *S)
{
	int p;
	if( strcmp (S,"\n") == 0)
	{
		nod->words ++;
		return;
	}
	
	/**pozitia in vectorul referinta edges*/
	p = firstS(S);
	
 	if( nod->edges[ p ] == 0 && nod != NULL )
	{
		nod->edges[ p ] = new Trie;
		nod->nr_fii ++;
	}
	
	Add(nod->edges[ p ], S + 1);
}

int Del(Trie *nod, char *S)
{
	int p;
	p = firstS(S);
	if( strcmp (S,"\n") == 0)
	{
		nod->words --;
	}
	else if(Del(nod->edges[ p ], S + 1 ))
	{
		nod->nr_fii --;
		nod->edges[ p ] = 0;
	}
	
	if(nod->words == 0 && nod->nr_fii == 0 && nod != T)
	{
		delete nod;
		return 1;
	}
	return 0;
}

int apar(Trie *nod, char *S)
{
	int p;
	if( strcmp (S,"\n") == 0)
	{
		return nod->words;
	}
	p = firstS(S);
	if(nod->edges[ p ])
		return apar(nod->edges[ p ], S+1);
	return 0;
}

int pref(Trie *nod, char *S,int length)
{
	int p;
	if( strcmp (S,"\n") == 0)
	{
		return length;
	}
	else
	{	
		p = firstS(S);
		if( nod-> edges[ p ] != 0)
			return pref(nod->edges[ p ], S+1,length+1 );
		else return length;
	}
}

void citire(Trie * T)
{
	FILE *f=fopen("trie.in","r"), *g=fopen("trie.out","w");
	char s[25];
	
	fgets(s,25,f);
	
	while(!feof(f))
	{
		switch(s[0])
		{
		case '0': Add(T,s+2); break;
		case '1': Del(T,s+2); break;
		case '2': fprintf(g,"%d\n",apar(T,s+2)); break;
		case '3': fprintf(g,"%d\n",pref(T,s+2,0)); break;			
		}	
	fgets(s,25,f);	
	}
	fclose(f);	
	fclose(g);	
}


int main()
{
	citire(T);

return 0;
}