#ifndef _CRT_NONSTDC_NO_WARNINGS
#define _CRT_NONSTDC_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

class TrieNode {
public:
	int wordCount;
	map<char, TrieNode*>childs;
	TrieNode() :wordCount{ 0 } {};
	~TrieNode() {};
};

class Trie {
private:
	TrieNode* TrieRoot;

	bool deleteWord(TrieNode* root, const string& word, const int& index);
	void destroyTrie(TrieNode* root);
public:

	Trie() { TrieRoot = new TrieNode(); }
	~Trie() { destroyTrie(TrieRoot); }

	void Adauga(const string& word);
	void Sterge(const string& word);
	int WordCount(const string& word);
	int SearchPrefix(const string& word);
};


void Trie::destroyTrie(TrieNode* root) {
	if (root == nullptr) return;
	for (auto child : root->childs) destroyTrie(child.second);
	delete(root);
	root = nullptr;
}

void Trie::Adauga(const string& word) {
	int size = (int)word.size();
	auto curent = this->TrieRoot;

	for (int i = 0; i < size; i++) {
		auto it = curent->childs.find(word[i]);
		if (it == curent->childs.end()) curent->childs[word[i]] = new TrieNode();
		curent = curent->childs[word[i]];
	}
	curent->wordCount++;
}

int Trie::WordCount(const string& word) {
	int size = (int)word.size();
	auto curent = this->TrieRoot;

	for (int i = 0; i < size; i++) {
		auto it = curent->childs.find(word[i]);
		if (it == curent->childs.end()) return 0;
		curent = curent->childs[word[i]];
	}
	return curent->wordCount;
}


int Trie::SearchPrefix(const string& word) {
	int size = (int)word.size();
	auto curent = this->TrieRoot;
	int prefix = 0;

	for (int i = 0; i < size; i++) {
		auto it = curent->childs.find(word[i]);
		if (it == curent->childs.end()) break;
		curent = curent->childs[word[i]];
		prefix++;
	}
	return prefix;
}

void Trie::Sterge(const string& word) {
	deleteWord(this->TrieRoot, word, 0);
	if (TrieRoot == nullptr) TrieRoot = new TrieNode();
}

bool Trie::deleteWord(TrieNode* root, const string& word, const int& index) {
	int size = (int)word.size();
	
	if (index == size) {
		root->wordCount--;
		return(root->wordCount == 0 && root->childs.size() == 0);
	}

	auto node = root->childs[word[index]];
	bool shouldBeDeleted = deleteWord(node, word, index + 1);
	
	if (shouldBeDeleted) {
		root->childs.erase(word[index]);
		delete(node);
		node = nullptr;
		return (root->childs.size() == 0 && root->wordCount == 0);
	}
	return false;
}

int main() {

	ifstream fin("trie.in");
	ofstream fout("trie.out");
	
	int code;
	string word;
	Trie trie;

	while (fin.good()) {
		code = -1;
		fin >> code >> word;
		if (code == 0) trie.Adauga(word);
		else if (code == 1) trie.Sterge(word);
		else if (code == 2) fout << trie.WordCount(word) << "\n";
		else if (code == 3) fout << trie.SearchPrefix(word) << "\n";
	}

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

#endif //_CRT_NONSTDC_NO_WARNINGS