#include<fstream>
using namespace std;
#define Nmax 22
char s[Nmax];
int op;

struct nod
{
	int nrc,nrf;
	nod *fiu[30];
}*rad,*p;

void parcurg(nod *p,char poz)
{
	
	if(p)
	{
	if(p!=rad)	printf("%c ",poz);
		for(int i=0;i<26;i++)
			parcurg(p->fiu[i],i+'a');
	}
}
void init(nod *p)
{
	p->nrc=0;
	p->nrf=0;
	for(int i=0;i<26;i++)
		p->fiu[i]=NULL;
}
void adauga(nod *c,char s[Nmax],int poz)
{
	
	if(s[poz]!='\0')
	{
		if(c->fiu[s[poz]-'a']==NULL)
		{
			p=new nod;
			init(p);
			c->nrf++;
			c->fiu[s[poz]-'a']=p;
			
		}
		adauga(c->fiu[s[poz]-'a'],s,poz+1);
	}
	else
		c->nrc++;
}

int aparitii(nod *c,char s[],int poz)
{
	
	if(s[poz]=='\0')
		return c->nrc;
	else
		if(c->fiu[s[poz]-'a'])
			return aparitii(c->fiu[s[poz]-'a'],s,poz+1);
		else
			return 0;
}

void sterge(nod *c,char s[],int poz)
{
	if(s[poz]!='\0')
	{	sterge(c->fiu[s[poz]-'a'],s,poz+1);
		if(c->fiu[s[poz]-'a']->nrc==0 && c->fiu[s[poz]-'a']->nrf==0 && c->fiu[s[poz]-'a']!=rad)
		{
			c->nrf--;
			c->fiu[s[poz]-'a']=NULL;
			delete c->fiu[s[poz]-'a'];
		}
	}
	else
		c->nrc--;

}

int prefix(nod *c,char s[],int poz)
{
	if(c->fiu[s[poz]-'a'] && s[poz]!='\0')
		return prefix(c->fiu[s[poz]-'a'],s,poz+1);
	else	return poz;
}

int main()
{
	ifstream f("trie.in");
	ofstream g("trie.out");
	rad=new nod;
	init(rad);
	while(f>>op>>s)
	{
				
		switch(op)
		{
		case 0:adauga(rad,s,0);break;
		case 1:sterge(rad,s,0);break;
		case 2:g<<aparitii(rad,s,0)<<'\n';;break;
		case 3:g<<prefix(rad,s,0)<<'\n';break;
		}
	}
	
	//parcurg(rad,'*');
	return 0;
}