#include <fstream>
#include <map>
#include <iostream>

using std::map;
using std::string;
std::ifstream in("trie.in");
std::ofstream out("trie.out");

struct node {
	int aparitii;
	map<char, node*> legaturi;

	node() : aparitii(0) {  legaturi = map<char, node*>(); }
};
node *root = new node;

void Add(string toAdd);
bool Delete(node* pos, string toDelete);
int CommonPrefix(node *pos, string toFindCommonPrefix, int commonPrefix = 0);
int Apparitions(node *pos, string toFindApparitions);

enum Operatie {
	Adauga = 0,
	Sterge = 1,
	TiparesteAparitii = 2,
	TiparirePrefixComun = 3
};
Operatie readEnum() {
	int x;
	in >> x;
	return (Operatie)x;
}

int main() {
	while (true) {
		if (in.eof()) break;

		Operatie op;
		string cuvant;

		op = readEnum();
		in >> cuvant;

		switch (op) {
			case Adauga:
				Add(cuvant);
				break;

			case Sterge:
				Delete(root, cuvant);
				break;

			case TiparesteAparitii:
				out << Apparitions(root, cuvant) << '\n';
				break;

			case TiparirePrefixComun:
				out << CommonPrefix(root, cuvant) << '\n';
				break;
		}
	}

	return 0;
}

int Apparitions(node *pos, string toFindApparitions) {
	if (toFindApparitions.empty()) return pos->aparitii;
	if (pos == nullptr) return 0;

	node *next = pos->legaturi[toFindApparitions[0]];
	return Apparitions(next, toFindApparitions.erase(0, 1));
}

int CommonPrefix(node *pos, string toFindCommonPrefix, int commonPrefix) {
	if (pos == nullptr) return commonPrefix - 1;
	if (toFindCommonPrefix.empty()) return -1;

	node* next = pos->legaturi[toFindCommonPrefix[0]];
	int resultFromPrevious = CommonPrefix(next, toFindCommonPrefix.erase(0, 1), commonPrefix + 1);

	if (resultFromPrevious >= 0) return resultFromPrevious;
	else return pos->aparitii == 0 ? -1 : commonPrefix;
}

bool Delete(node* pos, string toDelete) {
	if (toDelete.size() > 1) {
		node* next = pos->legaturi[toDelete[0]];
		bool previousNeedsToBeDeleted = Delete(next, toDelete.erase(0, 1));
		if (!previousNeedsToBeDeleted) return false;
	}
	pos->legaturi.erase(pos->legaturi.find(toDelete[0]));
	return pos->legaturi.empty();
}

void Add(string toAdd) {
	node* current = root;
	for (char i : toAdd) {
		if (current->legaturi.count(i) == 0 || current->legaturi[i] == nullptr) current->legaturi[i] = new node;
		current = current->legaturi[i];
	}
	current->aparitii++;
}