Implement a Trie with Prefix Search
Extend a trie to support checking whether any word starts with a given prefix.
Input format
The first line contains N. The next N lines contain words. The next line contains Q. The next Q lines contain queries.
Output format
For each query, print true if any word starts with the query prefix, false otherwise.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
3
wocyshsi nzf gz
2
w tzgngcvqExpected output
true
falseExample 2
Input
6
opuz vjtphyw mort nnmreysz wrrssa b
8
mort mor vj b mpwwkra xikrx pn iExpected output
true
true
true
true
false
false
false
false