#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;

//26 de litere mici.adica 26 de fii

class Nod{
public:
    int End;
    Nod *Fiu[26];
    int Nr_Fii;
    Nod(){
        Nr_Fii=0;
        End=0;
        memset(Fiu,0,sizeof(Fiu));
    }
};

class Trie{
private:
    Nod *Head;
public:
    Trie(){
        Head=new Nod;
    }
    void Inserare(Nod *nod,char *s);
    void Apel(const char *fis);
    int Find(Nod *nod,char *s);
    int Sterge(Nod *nod,char *s);
    int Prefix(Nod *nod,char *s,int lg);
};

void Trie::Inserare(Nod *nod,char *s){

    if(s[0]==0){
        nod->End++;

    }
    else{
        if(nod->Fiu[s[0]-'a']==NULL){
            nod->Fiu[s[0]-'a']=new Nod;
            nod->Nr_Fii++;
        }

        Inserare(nod->Fiu[s[0]-'a'],s+1);

    }
}

int Trie::Sterge(Nod *nod,char *s){
    if(s[0]==0){
        nod->End--;
    }
    else
        if(Sterge(nod->Fiu[s[0]-'a'],s+1)){
            nod->Nr_Fii--;
            nod->Fiu[s[0]-'a']=0;
    }
    if(nod->End==0 && nod->Nr_Fii==0 && nod!=Head){
        delete nod;
        return 1;
    }
    return 0;

}

void Trie::Apel(const char *fis){
    int x;
    char s[20];
    ifstream f(fis);
    ofstream g("trie.in");
    f>>x;
    while(x>=0 && x<=3){
        if(!x){
            memset(s,0,sizeof(s));
            f>>s;
            Inserare(Head,s);
        }

            else if(x==2){
                memset(s,0,sizeof(s));
                f>>s;
                g<<Find(Head,s)<<endl;
            }

                else if(x==1){
                    memset(s,0,sizeof(s));
                    f>>s;
                    Sterge(Head,s);
                }
                    else {
                        memset(s,0,sizeof(s));
                        f>>s;
                        g<<Prefix(Head,s,0)<<endl;
                    }

        f>>x;
    }
    f.close();
    g.close();

}

int Trie::Find(Nod *nod,char *s){
     if(s[0]==0){
        return nod->End;
     }

     if(nod->Fiu[s[0]-'a']!=NULL)
            Find(nod->Fiu[s[0]-'a'],s+1);
     else
        return 0;

}

int Trie::Prefix(Nod *nod,char *s,int lg){
    if(s[0]==0 || nod->Fiu[s[0]-'a']==0)
        return lg;
    return Prefix(nod->Fiu[s[0]-'a'],s+1,lg+1);
}

int main(){
    Trie A;
    A.Apel("trie.out");


    return 0;
}