#include <bits/stdc++.h>
using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");

struct nod{
    nod* parent;
    bool endictor;
    int frecv;
    //struct{char litera,nod* next}urmator;
    unordered_map<char,nod*> urmmat;
}*rad;
int crabism;
void ins(char v[]){
    nod* current=rad;
    for(int i=0;i<=strlen(v);i++){
        cout<<v[i]<<' '<<current->urmmat.count(v[i])<<' ';
        if(i==strlen(v)){
            cout<<"end"<<'\n';
            current->endictor=true;
            current->frecv++;
            return;
        }
        if(current->urmmat.count(v[i])){
            cout<<"c1"<<'\n';
            current=current->urmmat[v[i]];
        }
        else
        {
            cout<<"c2"<<'\n';
            nod*gina=new nod;
            gina->endictor=false;
            gina->frecv=0;
            gina->parent=current;
            gina->urmmat.clear();
            current->urmmat[v[i]]=gina;
            current=current->urmmat[v[i]];
        }
    }
}
void del(char v[]){
    nod* current=rad;
    for(int i=0;i<strlen(v);i++)
        current=current->urmmat[v[i]];
    current->frecv--;
    if(current->frecv==0){
        current->endictor=0;
        int it=strlen(v)-1;
        while(!current->endictor){
            current=current->parent;
            delete current->urmmat[v[it]];
            current->urmmat[v[it]]=NULL;
        }
    }
}
void afisarefr(char v[]){
    nod* current=rad;
    bool nuexistapreamare=0;
    for(int i=0;i<strlen(v) && current!=NULL;i++){
        cout<<v[i]<<' ';
        current=current->urmmat[v[i]];
    }
    if(current==NULL){fout<<0<<'\n';return;}
    fout<<current->frecv<<'\n';
}
void comparare(char v[]){
    int los=0;
    nod* current=rad;
    for(int i=0;i<strlen(v)-1;i++){
        current=current->urmmat[v[i]];
        if(current->endictor)
            los=i+1;
    }
    current=current->urmmat[v[strlen(v)-1]];
    if(!current->urmmat.empty())los=strlen(v);
    fout<<los<<'\n';
}
int main()
{
    int x;
    rad=new nod;
    rad->endictor=0;rad->frecv=0;
    rad->urmmat.clear();
    rad->parent=NULL;
    char word[67];
    while(fin>>x>>word){
        if(x==0)ins(word);
        if(x==1)del(word);
        if(x==2)afisarefr(word);
        if(x==3)comparare(word);
    }
    return 0;
}