A prefix of a word is a piece taken from its start: "c", "ca", "car" and "cart" are the prefixes of "cart". Build a class Trie that stores words and answers two questions about them. Each call must take time that depends only on the length of its word or prefix, not on how many words are stored.

• Trie() makes an empty store.
• insert(word) stores word. Storing a word twice is the same as storing it once.
• search(word) answers True exactly when word itself is one of the stored words. A prefix of a stored word does not count: after storing "cart", search("car") is False.
• starts_with(prefix) answers True exactly when at least one stored word begins with prefix. A stored word begins with itself.

Each Trie() you create starts empty and keeps its own words.