#include <fstream>
#include <iostream>

using namespace std;

const int NL = 26;
const int LC = 20;

struct nod
{
    nod* fii[NL];
    int nr_cuvinte, nr_fii;
    nod()
    {
        nr_cuvinte = nr_fii = 0;
        for (int i = 0; i < NL; i++)
        {
            fii[i] = NULL;
        }
    }
};

nod* adauga(nod* p, char cuv[])
{
    if (p == NULL)
    {
        p = new nod;
    }
    if (cuv[0] == '\0')///suntem la finalul cuvantului pe care-l adaugam
    {
        p->nr_cuvinte++;
        return p;
    }
    int poz_litera = (int)(cuv[0] - 'a');
    if (p->fii[poz_litera] == NULL)
    {
        p->nr_fii++;
    }
    p->fii[poz_litera] = adauga(p->fii[poz_litera], cuv + 1);
    return p;
}

nod* sterge(nod* p, char cuv[])
{
    if (cuv[0] == '\0')
    {
        if (p->nr_fii == 0 && p->nr_cuvinte == 1)///p este o frunza
        {
            delete p;
            p = NULL;
        }
        else
        {
            p->nr_cuvinte--;
        }
    }
    else
    {
        int poz_litera = (int)(cuv[0] - 'a');
        p->fii[poz_litera] = sterge(p->fii[poz_litera], cuv + 1);
        if (p->fii[poz_litera] == NULL)
        {
            p->nr_fii--;
        }
    }
    return p;
}

int aparitii(nod* p, char cuv[])
{
    if (p == NULL)
    {
        return 0;
    }
    if (cuv[0] == '\0')///suntem la finalul cuvantului verificat
    {
        return p->nr_cuvinte;
    }
    int poz_litera = (int)(cuv[0] - 'a');
    return aparitii(p->fii[poz_litera], cuv + 1);
}

int lung_prefix(nod* p, char cuv[])
{
    if (p == NULL)
    {
        return 0;
    }
    if (cuv[0] == '\0')///suntem la finalul cuvantului verificat
    {
        return 0;
    }
    int poz_litera = (int)(cuv[0] - 'a');
    int lungime = 0;
    if (p->fii[poz_litera] != NULL)
    {
        lungime = 1 + lung_prefix(p->fii[poz_litera], cuv + 1);
    }
    return lungime;
}

int main()
{
    ifstream in("trie.in");
    ofstream out("trie.out");
    char cuvant[LC+1];
    int tip;
    nod *radacina = NULL;
    int nr_afis = 0;
    while (in >> tip >> cuvant)
    {
        if (tip == 0)
        {
            radacina = adauga(radacina, cuvant);
        }
        else if (tip == 1)
        {
            radacina = sterge(radacina, cuvant);
        }
        else if (tip == 2)
        {
            nr_afis++;
            out << aparitii(radacina, cuvant) << "\n";
        }
        else///tip == 3
        {
            nr_afis++;
            out << lung_prefix(radacina, cuvant) << "\n";
        }
        /*
        if (nr_afis == 4195)
        {
            cout << tip << " " << cuvant << "\n";
        }
        */
    }
    in.close();
    out.close();
    return 0;
}