#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

struct Nod
{
    char litera;
    Nod* adresa[26];
    int capat;
    int fr;
    Nod()
    {
        fr=0;
        capat=0;
        memset(adresa,0,sizeof adresa);
        litera=0;
    }
};

stack<Nod> S;

Nod zero;

Nod gol;

int main()
{
    S.push(zero);
    char s[24];
    while(fin.getline(s,24))
    {
        if(s[0]=='0')///adaug cuvantul in arbore
        {
            ///cuvantul incepe de la s[2]
            int j=2;
            char ch=s[j]-'a';
            Nod* x;
            x=&zero;

            while((*x).adresa[ch]!=0)///cat timp exista cuvantul in graf
            {

                x=(*x).adresa[ch];///m am dus la ch
                (*x).fr++;
                j++;
                ch=s[j]-'a';
                if(ch<0)
                    break;
            }
            ///de acum in colo trebuie sa atribui locuri in graf
            while(s[j]!='\0')
            {

                ch=s[j]-'a';
                gol.litera=s[j];
                S.push(gol);
                (*x).adresa[ch]=&(S.top());
                x=&(S.top());
                (*x).fr++;
                j++;

            }
            (*x).capat++;
            //fout<<(*x).litera<<" "<<(*x).capat<<'\n';
            //fout<<(S.top()).litera<<" ";
        }
        else if(s[0]=='1')///elimin
        {
            int j=2;
            Nod* x;
            x=&zero;
            char ch=s[j]-'a';
            while((*x).adresa[ch]!=0)
            {
                x=(*x).adresa[ch];
                (*x).fr--;
                j++;
                ch=s[j]-'a';
                if(ch<0)
                    break;
            }
            (*x).capat--;
            fout<<(*x).capat<<" "<<(*x).litera<<"\n";
        }
        else if(s[0]=='2')///nr de aparitii
        {
            int j=2;
            Nod* x;
            x=&zero;
            char ch=s[j]-'a';
            while((*x).adresa[ch]!=0)
            {
                x=(*x).adresa[ch];
                j++;
                ch=s[j]-'a';
                if(ch<0)
                    break;
            }
            fout<<(*x).capat<<'\n';
        }
        else if(s[0]=='3')///cel mai lung prefix
        {
            int j=2;
            Nod* x;
            x=&zero;
            char ch=s[j]-'a';
            int nr=0;
            while((*x).adresa[ch]!=0)
            {
                x=(*x).adresa[ch];
                if((*x).fr<1)
                    break;
                nr++;
                j++;
                ch=s[j]-'a';
                if(ch<0)
                    break;
            }
            fout<<nr<<'\n';
        }
    }
    return 0;
}