#define fisier "trie"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

#include <unordered_map>
#include <string>
struct Arbore
{
    std::unordered_map<char, Arbore*> subarbori;
    int aparitii = 0;
    Arbore* tata = NULL;
    char muchie = 0;

    void afiseaza(int ind)
    {
        std::string
        indent(4*ind, ' '),
        indent2 = indent + "    ";

        out
        << indent << "{\n"
        << indent2 << "aparitii = " << aparitii << ",\n"
        << indent2 << "tata = " << tata << ",\n"
        << indent2 << "muchie = " << (muchie? muchie: '0') << ",\n"
        << indent2 << "nr_subarbori = " << subarbori.size() << ",\n\n"
        << indent2 << "subarbori =\n" << indent2 << "[\n";
        for (auto pr: subarbori)
        {
            out << indent2 << "\'" << pr.first << "\':\n";
            pr.second->afiseaza(ind + 2);
            out << ",\n";
        }
        out << indent2 << "]\n" << indent << "}";
    }

    Arbore* operator [] (const char chr)
    {
        Arbore*& subarb = subarbori[chr];
        if (!subarb)
            subarb = new Arbore;
        return subarb;
    }

    Arbore* operator [] (std::string str)
    {
        Arbore* curent = this;

        for (char chr: str)
        {
            Arbore* urmatorul = (*curent)[chr];
            if (!urmatorul->tata)
            {
                urmatorul->tata = curent;
                urmatorul->muchie = chr;
            }
            curent = urmatorul;
        }
        return curent;
    }

    void pop()
    {
        if (!subarbori.size() && !aparitii && tata)
        {
            tata->subarbori.erase(muchie);
            tata->pop();
            delete this;
        }
    }



    inline int vezi_aparitii(std::string str)
    {
        Arbore* arb = (*this)[str];
        int rt = arb->aparitii;
        arb->pop();
        return rt;
    }
    inline void incrementeaza(std::string str)
    {
        (*this)[str]->aparitii++;
    }
    inline void decrementeaza(std::string str)
    {
        Arbore* arb = (*this)[str];
        --arb->aparitii;
        arb->pop();
    }
    inline std::string prefix(std::string str)
    {
        Arbore* arb = (*this)[str];
        if (arb->subarbori.size() || arb->aparitii)
            return str;
        arb->pop();
        return prefix(str.substr(0, str.size()-1));
    }

} arbore;



int main()
{
    int op;
    std::string cuv;
    while (in >> op >> cuv)
    {
        switch (op)
        {
            case 0:
                arbore.incrementeaza(cuv);
                break;
            case 1:
                arbore.decrementeaza(cuv);
                break;
            case 2:
                out << arbore.vezi_aparitii(cuv) << '\n';
                break;
            case 3:
                out << arbore.prefix(cuv).size() << '\n';
                break;
        }
    }
}