#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct nod
{
    int nrcuv;                  //nr de cuvinte care se termina in nodul curent
    int nrfii;                     //nr de cuvinte care au acest prefix,adica trec prin nodul curent
    nod *v[26];                //pt fiecare litera a alfabetului
    nod()
    {
        nrfii=nrcuv=0;
        memset(v,0,sizeof(v));
    }
};
nod *T=new nod;
void insereaza(nod *t,char s[21],int i)
{
    if(i == strlen(s))
        {
            t->nrcuv++;
            return ;
        }
    if(t->v[s[i] - 'a'] == 0)
    {
        t->v[s[i] - 'a']=new nod;
        t->nrfii++;
    }
    insereaza(t->v[s[i] - 'a'],s,i+1);
}
int sterge(nod *t,char s[21],int i)
{
    if(i == strlen(s))
        t->nrcuv--;
    else if(sterge(t->v[s[i] - 'a'],s,i + 1))
                {
                    t->v[s[i] - 'a']=0;
                    t->nrfii--;
                }

             if(!t->nrcuv && !t->nrfii  && t!=T)
                    {
                        delete t;
                        return 1;
                    }
    return 0;
}
int numar_cuvinte(nod *t,char s[21],int i)
{
    if(i == strlen(s))
        return t->nrcuv;
    if(t->v[s[i] - 'a'])
        return numar_cuvinte(t->v[s[i] - 'a'],s,i + 1);
    return 0;
}
int numar_fii(nod *t,char s[21],int i)
{
    if(i == strlen(s) ||! t->v[s[i] - 'a'])
        return i;
    return numar_fii(t->v[s[i] - 'a'],s,i+1);
}
int main()
{
    FILE *f=fopen("trie.in","rt");
    FILE *g=fopen("trie.out","wt");
    int op;
    char cuv[21];
    while(!feof(f))
    {
        fscanf(f,"%i %s",&op,&cuv);
        switch(op)
        {
            case 0:insereaza(T,cuv,0);break;
            case 1:sterge(T,cuv,0);break;
            case 2:fprintf(g,"%i\n",numar_cuvinte(T,cuv,0));break;
            case 3:fprintf(g,"%i\n",numar_fii(T,cuv,0));
        }
    }
    fclose(f);
    fclose(g);
    return 0;
}