A trie (pronounced "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

Implement the Trie class:

• insert(word) — inserts string word into the trie.
• search(word) — returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• startsWith(prefix) — returns true if there is a previously inserted string that has the prefix prefix, and false otherwise.

Example:

Input:
insert apple
search apple
search app
startsWith app
insert app
search app

Output:
true
false
true
true

Constraints:

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix consist only of lowercase English letters.
• At most 3 × 10⁴ calls total.

Input format: One command per line.

Output format: Print a line for search and startsWith operations only.