#include <fstream>
#include <iostream>
#include <string.h>
#include <queue>

using namespace std;


const char infile[] = "trie.in";
const char outfile[] ="trie.out";

struct TrieNode
{
	int info;
	short childCount;

	TrieNode* child[26];

	TrieNode()
	{
		childCount= 0;
		info = 0;
		memset(child, 0, sizeof(child));
	}

	~TrieNode()
	{
		for(int i = 0; i < 26; i++)
		{
			if(child[i] != NULL)
			{
				delete child[i];
			}
		}
	}

};


class Trie
{
public:
	void addWord(char* word);
	void removeWord(char* word);
	int getWordCount(char* word);
	int getWordPrefix(char* word);

	void printToDot(ostream & stream);


protected:
private:
	TrieNode root;


};


void Trie::printToDot(ostream& stream)
{

    stream << "digraph Trie {\n";
    stream << "\t" << "graph [overlap=false];" << "\n";

    queue<TrieNode*> q;
    q.push(&this->root);

    TrieNode* current = &this->root;

    stream << "\t" << (int) current << "[label = \"" <<  current->info <<"\"];\n";

    while(q.empty() == false)
    {
        current = q.front();
        q.pop();

        for(int i = 0; i < 26; i++)
        {
            if(current->child[i] != NULL)
            {
                stream << "\t"
                       << (int) current->child[i]
                       << "[label = \""
                       << current->child[i]->info
                       << "\"];\n";

                stream << "\t"
                       << (int) current
                       << "->"
                       << (int) current->child[i]
                       << "[label = \""
                       << (char)(i + 'a')
                       << "\"];\n";

                q.push(current->child[i]);
            }
        }

    }

    stream << "}";

}


void Trie::addWord(char* word)
{
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			n->child[word[currentLevel] - 'a'] = new TrieNode();
			n->childCount++;
		}

		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}
	n->info++;

}

void Trie::removeWord(char* word)
{

	TrieNode* parent = &this->root;
	int letter = word[0] - 'a';

	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			return;
		}

		if ( n->childCount > 1 )
		{
			parent = n;
			letter = word[currentLevel] - 'a';
		}
		else if( n->info > 0)
		{
		    parent = n;
			letter = word[currentLevel] - 'a';
		}

		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}
	if(n->info > 0)
        n->info--;

	if(n->info == 0 && n->childCount == 0)
	{
		delete parent->child[letter];
		parent->child[letter] = NULL;
		parent->childCount--;
	}

}

int Trie::getWordCount(char* word)
{
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			return 0;
		}

		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}


	return n->info;
}

int Trie::getWordPrefix(char* word)
{
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			return currentLevel;
		}

		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}

	return currentLevel;
}

//#define _debug

int main(int argc, char* argv[])
{

	fstream fin(infile, ios::in);
	fstream fout(outfile, ios::out);

	Trie trie;

	char input[30];

    int result;

#ifdef _debug
    fstream dot;
    int counter = 0;
    char buff[100];
#endif

	while (fin.getline(input, 30))
	{


		short command = input[0] - '0';
		char* word = input + 2;



		switch (command)
		{
		case 0:

			trie.addWord(word);
#ifdef _debug
            sprintf(buff, "%05d_%s_%s.gv", counter, "add", word);
            counter++;
            dot.open(buff, ios::out);
            trie.printToDot(dot);
            dot.close();
#endif
			break;
		case 1:

			trie.removeWord(word);

#ifdef _debug
            sprintf(buff, "%05d_%s_%s.gv", counter, "remove", word);
            counter++;
            dot.open(buff, ios::out);
            trie.printToDot(dot);
            dot.close();
#endif
			break;
		case 2:

            result = trie.getWordCount(word);
			fout << result << "\n";
#ifdef _debug
            sprintf(buff, "%05d_%s_%s_result_%d.gv", counter, "count", word, result);
            counter++;
            dot.open(buff, ios::out);
            trie.printToDot(dot);
            dot.close();
#endif
			break;
		case 3:

            result = trie.getWordPrefix(word);
			fout << result << "\n";
#ifdef _debug
            sprintf(buff, "%05d_%s_%s_result_%02d.gv", counter, "prefix", word, result);
            counter++;
            dot.open(buff, ios::out);
            trie.printToDot(dot);
            dot.close();
#endif
			break;
		}

	}

	fin.close();
	fout.close();
}