class TrieNode {
public:
	// Initialize your data structure here.
	bool vis;
	TrieNode *ch[26];
	TrieNode() {
		vis = false;
		for (int i = 0; i < 26; i++) ch[i] = NULL;
	}
};

class Trie {
public:
	Trie() {
		root = new TrieNode();
	}

	// Inserts a word into the trie.
	void insert(string word) {
		if (word.empty()) return;
		TrieNode *x = root;
		int d = 0;
		Ite p = word.begin();
		while (p != word.end()) {
			d = *p - ‘a‘;
			if (!x->ch[d]) x->ch[d] = new TrieNode;
			x = x->ch[d];
			p++;
		}
		x->vis = true;
	}

	// Returns if the word is in the trie.
	bool search(string word) {
		TrieNode *x = root;
		int d = 0;
		Ite p = word.begin();
		while (p != word.end()) {
			d = *p - ‘a‘;
			if (!x || !x->ch[d]) return false;
			x = x->ch[d];
			p++;
		}
		return x->vis;
	}

	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix) {
		TrieNode *x = root;
		int d = 0;
		Ite p = prefix.begin();
		while (p != prefix.end()) {
			d = *p - ‘a‘;
			if (!x || !x->ch[d]) return false;
			x = x->ch[d];
			p++;
		}
		return x != NULL;
	}

private:
	TrieNode* root;
	typedef string::iterator Ite;
};