#include <iostream>
#include <string>
using namespace std;

const int ALPHABET_SIZE = 26;

// óçåë
struct TrieNode
{
	struct TrieNode *children[ALPHABET_SIZE];

	// isEndOfWord èñòèííî åñëè íà ýòîé óçëå ñòðîêà çàêàí÷èâàåòñÿ 
	bool isEndOfWord;
};

// Âîçâðàùàåò íîâûé óçåë
struct TrieNode *getNode(void)
{
	struct TrieNode *pNode = new TrieNode;

	pNode->isEndOfWord = false;

	for (int i = 0; i < ALPHABET_SIZE; i++)
		pNode->children[i] = NULL;

	return pNode;
}
//Âñòàâëÿåò íîâóþ ñòðîêó
void insert(struct TrieNode *root, string key)
{
	struct TrieNode *pCrawl = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!pCrawl->children[index])
			pCrawl->children[index] = getNode();

		pCrawl = pCrawl->children[index];
	}

	// ïîìå÷àåì ïîñëåäíèé ñëîâ
	pCrawl->isEndOfWord = true;
}

// Ïîèñê êëþ÷à
bool search(struct TrieNode *root, string key)
{
	struct TrieNode *pCrawl = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!pCrawl->children[index])
			return false;

		pCrawl = pCrawl->children[index];
	}

	return (pCrawl != NULL && pCrawl->isEndOfWord);
}

int main()
{
	struct TrieNode *root = getNode();
	       

return 0;
}