A routing table stores n dictionary entries. For each of q query strings, find the longest dictionary entry that is a prefix of the query (an entry w matches a query x if x starts with w). Because the matching entries of a given query all have distinct lengths, the longest match is unique.
If no dictionary entry is a prefix of the query, print NONE. All strings consist of lowercase English letters only. Duplicate dictionary entries are allowed and behave like a set.
Input format
Line 1: an integer n.
Line 2: n space-separated dictionary entries.
Line 3: an integer q.
Line 4: q space-separated query strings.
Output format
Print q lines; line i is the longest dictionary entry that is a prefix of query i, or NONE.
Constraints
- 1 <= n <= 100000
- 1 <= q <= 100000
- Each string has length 1..30, lowercase English letters.