Trie Data Structure: Prefix Search

Implement a Trie, a tree-like data structure that is extremely efficient for storing and retrieving strings. In this problem, you will build a Trie that supports two operations:

• insert word: Inserts a word into the Trie.
• startswith prefix: Checks if there exists any word in the Trie that starts with the given prefix.

The input will be read from standard input (stdin) and for every startswith query, your program should output True if there exists at least one word having the specified prefix, otherwise False. All words consist of lowercase letters.

inputFormat

The input is given via stdin. The first line contains an integer Q, representing the number of queries. Each of the following Q lines contains a query in one of the following formats:

• insert word • startswith prefix

Note: There is no output for insert commands; output is expected only for startswith commands.

outputFormat

For each query of type 'startswith', print a single line to stdout containing either 'True' or 'False', indicating whether or not any word in the Trie starts with the given prefix.## sample

4
insert apple
startswith app
startswith apl
startswith apple

True
False
True