Implement Trie

Problem statement

An autocomplete service stores a growing dictionary of lowercase words. It must distinguish a complete stored word from a prefix that could lead to one, so a simple membership list is not enough for every query. Your task Implement a trie with insert word, search word and startsWith prefix. search is true only for complete inserted words; startsWith is true when at least one inserted word begins with the prefix. Important details Reinserting a word leaves membership unchanged. A path in the trie can exist without ending a complete word, so maintain an end-of-word marker. Each operation should take time proportional to its text length. Worked example After insert apple, search app is false but startsWith app is true. After insert app, search app becomes true.

Input format

First line: q. Next q lines: operation text.

Output format

Print true or false for each search and startsWith, one per line. Print EMPTY if there are no queries.

Constraints

1 <= q <= 30000; 1 <= word/prefix length <= 2000; lowercase English letters.

Sample input

5
insert apple
search app
startsWith app
insert app
search app

Sample output

false
true
true