#include<bits/stdc++.h>
using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

class Trie {
private:	
	struct node{
		int passcount;
		int endcount;
		array<node*, 26> children = {};
	};
	static int get_id(char c) {
		return c-'a';
	}
	node* root = new node;
public:
	void insert(string_view s) {
		auto aux = root;
		aux->passcount++;
		for(auto ch: s) {
			int i = get_id(ch);
			if(!aux->children[i]) aux->children[i] = new node;
			aux = aux->children[i];
			aux->passcount++;
		}
		aux->endcount++;
	}
	bool contains(string_view s) {
		auto aux = root;
		for(auto ch: s) {
			int i = get_id(ch);
			if(!aux->children[i]) return false;
			aux = aux->children[i];
		}
		return aux->endcount;
	}
	string longest_prefix(string_view s) {
		auto aux = root;
		string ans = {};
		for(auto ch:s) {
			int i = get_id(ch);
			if(aux->children[i]) {
				ans+=ch;
			} else return ans;
		}
		return ans;
	}

	void erase_rec(node*& node, string_view s, int depth) {
		if(depth == s.size()) {
			node->endcount--;
			node->passcount--;
		} else {
			int i = get_id(s[depth]);
			erase_rec(node->children[i],s, depth+1);
			node->passcount--;
		}
		if(node->passcount || node->endcount) return;
		for(auto child: node->children) {
			if(child) return;
		}
		delete node;
		node = nullptr;
		return;
	}

	bool erase(string_view s) {
		if(!contains(s)) return false;
		erase_rec(root, s, 0);
		return true;
	}
};

int main(void) {
	Trie trie;
	int cmd;
	string word;
	while(fin>>cmd) {
		fin>>word;
		switch(cmd) {
			case 0: {
				trie.insert(word);
			}
			case 1: {
				trie.erase(word);
			} 
			case 2: {
				trie.contains(word);
			}
			case 3: {
				fout<<trie.longest_prefix(word);
			}
		}
	}
}