Implement Trie (Prefix Tree)

Implement a Trie with `insert(word)`, `search(word)`, and `startsWith(prefix)` methods for lowercase English words.

Input Format

N/A (Design problem).

Output Format

N/A.

Constraints

• Total operations <= 10^4; word length <= 1000.

Examples