#include <iostream>
#include <fstream>
#include <string>

struct TrieNode
{
    TrieNode *TrieNodeChildren[26];
    int aparitii;
    int nrOfChildrenNodes;
};

void insertString(std::string st,TrieNode* Trie);
int nrOfAparitions(std::string st, TrieNode* Trie);
struct TrieNode *createNode();
int search(std::string st, TrieNode* Trie);
int del(struct TrieNode* Trie,std::string st,int index);
int prefixSearch(std::string st, TrieNode* Trie);

std::fstream f("trie.in",std::ios::in);
std::ofstream g("trie.out");

int main()
{
    std::string st;

    int choice;

    TrieNode *T = createNode();
    T->aparitii++;

    while(f>>choice)
        {
        f>>st;
        switch(choice)
         {
     case 0:
         insertString(st,T);
        break;
     case 1:
         del(T,st,0);
        break;
     case 2:
         g<<search(st,T)<<"\n";
        break;
     case 3:
         g<<prefixSearch(st,T)<<"\n";
        break;
         }
        }

    return 0;
}

int prefixSearch(std::string st, TrieNode* Trie)
{
    int length = st.length(),indexString=0,stringCharToNumber;

    TrieNode* currentTrie = Trie;

    for(;indexString<length;++indexString)
        {
         stringCharToNumber = (int)st[indexString]-(int)'a';

      if(currentTrie->TrieNodeChildren[stringCharToNumber] == NULL)
         return indexString;
         else currentTrie = currentTrie->TrieNodeChildren[stringCharToNumber];
        }

    return indexString;
}

void insertString(std::string st,TrieNode* Trie)
{
   int length = st.length(),indexString=0,stringCharToNumber;

   TrieNode* currentTrie = Trie;

   for(;indexString<length;++indexString)
    {
      stringCharToNumber = st[indexString]-'a';
      if(currentTrie->TrieNodeChildren[stringCharToNumber] == NULL)
        {
         currentTrie->TrieNodeChildren[stringCharToNumber] = createNode();
         currentTrie->nrOfChildrenNodes+=1;
        }
      currentTrie = currentTrie->TrieNodeChildren[stringCharToNumber];
    }
    currentTrie->aparitii+=1;
}

struct TrieNode *createNode()
{
    TrieNode *newNode = new TrieNode;

    for(int i = 0; i<26;++i)
        {
        newNode->TrieNodeChildren[i] = NULL;
        }
    newNode->aparitii = 0;

    return newNode;
};

int search(std::string st, TrieNode* Trie)
{
   int length = st.length(),indexString=0,stringCharToNumber;

   TrieNode* currentTrie = Trie;


    for(;indexString<length;++indexString)
        {
         stringCharToNumber = (int)st[indexString]-(int)'a';

        if(currentTrie->TrieNodeChildren[stringCharToNumber] == NULL)
         return 0;
         else currentTrie = currentTrie->TrieNodeChildren[stringCharToNumber];
        }
    return currentTrie->aparitii;
}


int del(struct TrieNode* Trie,std::string st,int index)
{
   if(index == st.size()-1)
    {
       if(Trie->aparitii>1 || Trie->nrOfChildrenNodes)
        {
         --Trie->aparitii;
         return 0;
        }
        else
        {
                delete Trie;
                return 1;
        }
    }
    else
        {
        if(del(Trie->TrieNodeChildren[(int)st[index]-(int)'a'],st,index+1))
            {
            --Trie->nrOfChildrenNodes;
            Trie->TrieNodeChildren[(int)st[index]-(int)'a'] = NULL;
            if(Trie->aparitii == 0 && Trie->nrOfChildrenNodes == 0)
                {
               delete Trie;
               return 1;
                }
            else return 0;
            }
        else return 0;
        }
}