#include <bits/stdc++.h>

using namespace std;

ifstream f("trie.in");
ofstream g("trie.out");

struct copac
{
    copac* copii[26];
    int valoare;
    copac(){
        for (int i=0; i<26; ++i)
            copii[i]=0;
        valoare=0;
    }
};
copac *root;

int tip, l;
char sir[25];

string s;

void adaugare()
{

    copac *nod=root;
    for (int i=0; i<l; ++i)
    {
        if (nod->copii[sir[i]-'a']==0)
            nod->copii[sir[i]-'a']=new copac;
        nod=nod->copii[sir[i]-'a'];
    }
    nod->valoare++;
}

void stergere(copac *&node, int ind)
{
    if(ind==l)
    {
        if (node->valoare>0)
        {
            node->valoare--;
            if (node->valoare==0)
            {
                int nr_copii=0;
                for (int i=0; i<26; ++i)
                    if (node->copii[i])
                        nr_copii++;
                if(nr_copii==0 && node!=root)
                {
                    node->valoare=0;
                    node=0;
                    delete node;
                }
            }
        }
        return;
    }
    stergere(node->copii[sir[ind]-'a'],ind+1);
    int nr_copii;
    if (node->valoare==0)
    {
        int nr_copii=0;
        for (int i=0; i<26; ++i)
            if (node->copii[i])
                nr_copii++;
        if(nr_copii==0 && node!=root)
        {
            node->valoare=0;
            node=0;
            delete node;
        }
    }
}

void afisare(copac *nod)
{
    int nr_copii=0;
    if(nod->valoare)
        cout << s <<' '<<nod->valoare << '\n';
    for (int i=0; i<26; ++i)
    {
        if (nod->copii[i])
        {
            s.push_back(i+'a');
            afisare(nod->copii[i]);
            s.pop_back();
        }
    }

}

void afisare2(copac *nod, int ind)
{
    if (ind==l)
    {
        g << nod->valoare << '\n';
        return;
    }
    if (nod->copii[sir[ind]-'a'])
    {
        afisare2(nod->copii[sir[ind]-'a'],ind+1);
    }
    else
    {
        g << 0 << '\n';
        return;
    }

}

void rez3(copac *nod, int ind, int valoare)
{
    if (valoare==l)
    {
        g << valoare << '\n';
        return;
    }
    if(nod->copii[sir[ind]-'a'])
        rez3(nod->copii[sir[ind]-'a'],ind+1,valoare+1);
    else
    {
        g << valoare << '\n';
        return;
    }
}

int main()
{
    root=new copac;
    for (int i=0; i<26; ++i)
        root->copii[i]=0;
    while(f>>tip)
    {
        f >> sir;
        l=strlen(sir);
        if(tip==0)
        {
            adaugare();
        }
        else if (tip==1)
        {
            stergere(root,0);
        }
        else if (tip==2)
        {
            afisare2(root,0);
        }
        else if (tip==3)
        {
            rez3(root,0,0);
        }
    }
   // afisare(root);
    return 0;
}