Implement Trie (Prefix Tree)

Design a Trie (prefix tree) class that stores lowercase words and supports these operations:

• Trie() creates an empty trie.
• insert(word) stores word. Inserting the same word again has no extra effect.
• search(word) returns True if word itself was inserted earlier, and False otherwise. Being a prefix of an inserted word is not enough.
• startsWith(prefix) returns True if at least one inserted word begins with prefix (a word counts as beginning with itself), and False otherwise.

The examples list the calls made in order, and the output lists each call's return value (None for the constructor and insert).