#include <map>
#include <string>
class Trie_std {
private:
	struct diag {
		std::map<char, diag*> son;
		diag* father;
		char ch;
		int endcnt;
		diag()
			: son(), ch(0), endcnt(0), father(nullptr) {}
		diag(const std::map<char, diag*>& son, char ch, int endcnt)
			: son(son), ch(ch), endcnt(endcnt), father(nullptr) {}
	} *root;
public:
	Trie_std() {
		root = new(diag);
	}
	void insert(std::string x) {
		int siz = x.size();
		diag* now = root;
		for (int i = 0; i < siz; i++) {
			if ((now->son.find(x[i])) == (now->son.end()))
				now->son[x[i]] = new(diag),
				now->son[x[i]]->father = now,
				now->son[x[i]]->ch = x[i];
			now = now->son[x[i]];
		}
		now->endcnt++;
	}
	bool find(std::string x) {
		int siz = x.size();
		diag* now = root;
		for (int i = 0; i < siz; i++) {
			if (now->son.find(x[i]) == now->son.end())
				return false;
			now = now->son[x[i]];
		}
		if (now->endcnt)
			return true;
		else
			return false;
	}
	bool erase(std::string x) {
		int siz = x.size();
		diag* now = root;
		for (int i = 0; i < siz; i++) {
			if (now->son.find(x[i]) == now->son.end())
				return false;
			now = now->son[x[i]];
		}
		diag* t;
		now->endcnt--;
		while (siz--) {
			t = now->father;
			if (!(now->son.size())) {
				t->son.erase(now->ch);
				delete now;
			}
			else return true;
			now = t;
		}
		return true;
	}
};


class Trie_lst {
private:
	struct diag {
		std::map<char, diag*> son;
		diag* father;
		char ch;
		int endcnt;
		diag()
			: son(), ch(0), endcnt(0), father(nullptr) {}
		diag(const std::map<char, diag*>& son, char ch, int endcnt)
			: son(son), ch(ch), endcnt(endcnt), father(nullptr) {}
	} *root;
public:
	Trie_lst() {
		root = new(diag);
	}
	void insert(char* x, int siz) {
		diag* now = root;
		for (int i = 0; i < siz; i++) {
			if ((now->son.find(x[i])) == (now->son.end()))
				now->son[x[i]] = new(diag),
				now->son[x[i]]->father = now,
				now->son[x[i]]->ch = x[i];
			now = now->son[x[i]];
		}
		now->endcnt++;
	}
	bool find(char* x, int siz) {
		diag* now = root;
		for (int i = 0; i < siz; i++) {
			if (now->son.find(x[i]) == now->son.end())
				return false;
			now = now->son[x[i]];
		}
		if (now->endcnt)
			return true;
		else
			return false;
	}
	bool erase(char* x, int siz) {
		diag* now = root;
		for (int i = 0; i < siz; i++) {
			if (now->son.find(x[i]) == now->son.end())
				return false;
			now = now->son[x[i]];
		}
		diag* t;
		now->endcnt--;
		while (siz--) {
			t = now->father;
			if (!(now->son.size())) {
				t->son.erase(now->ch);
				delete now;
			}
			else return true;
			now = t;
		}
		return true;
	}
};