Implement a Trie (Insert, Search)

Implement a Trie (Insert, Search)

Implement a trie data structure supporting insertion and exact-word search.

Input format

The first line contains N. The next N lines contain words (lowercase, ≤8 chars). The next line contains Q. The next Q lines contain queries.

Output format

For each query, print true if the exact word is in the trie, 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.

4
zkw ianmyiq ewgnislj e
10
ewgnislj ewgnislj e ianmyiq ewgnislj yzgraqnm sxqso rqf r jltdzq

true
true
true
true
true
false
false
false
false
false

2
l xyqrr
13
l l xyqrr xyqrr l xyqrr l ur fkzupl rsougzy x zwjn cwwtn

true
true
true
true
true
true
true
false
false
false
false
false
false