Implement a Trie

Build a trie and run a list of operations on it, starting empty. Each operation is a string: "insert w" adds the word w, "search w" asks whether the whole word w was inserted, and "starts w" asks whether some inserted word starts with w. Return the answers of all search and starts operations, in order, as booleans.

For ["insert apple", "search apple", "search app", "starts app", "insert app", "search app"] the answer is [True, False, True, True].

Examples

Example 1

Input:

run_trie(['insert apple', 'search apple', 'search app', 'starts app', 'insert app', 'search app'])

Output:

[True, False, True, True]

Example 2

Input:

run_trie([])

Output:

[]

Constraints

• 0 <= len(ops) <= 100000
• Words are lower-case letters, 1 to 20 long.