Frugal Search

Time limit1sMemory limit128 MB

Summary

Given a word list and queries of bar-separated terms with unsigned, plus, and minus letters, output the lexicographically smallest matching word or NONE for each query.

Level: Medium4 of 10
Topics: String, Implementation, Brute force, Sorting
Solved: No attempts yet

Problem

Write a search engine that, given a query, searches a collection of words and returns the lexicographically smallest word that matches the query (the matching word that would appear first in an English dictionary).

A query is a sequence of one or more terms separated by single vertical bars (|).

A term is one or more letters followed by zero or more signed letters. A signed letter is either +s (a positive letter) or -s (a negative letter), where s is a single letter. All letters are lowercase, and no letter appears more than once within a term. A query contains no spaces. The plain letters at the start of a term are its unsigned letters.

A term matches a word if:

the word contains at least one of the term's unsigned letters, and
the word contains all of the term's positive letters, and
the word contains none of the term's negative letters.

A query matches a word if at least one of its terms matches the word.

Input

The input consists of one or more test cases, followed by a line containing only # that marks the end of the input.

Each test case consists of:

1 to 100 words, each on its own line, followed by a line containing only * that marks the end of the word list;
one or more queries, each on its own line, followed by a line containing only ** that marks the end of the test case.

Each word consists of 1 to 20 lowercase letters. All words within a test case are distinct. Each query follows the definition above and is 1 to 79 characters long.

Output

For each query, output a single line containing the lexicographically smallest word in that test case that matches the query, or the word NONE if no word matches. After all queries of a test case, output a single line containing only a dollar sign ($).

Examples7

Example 1

Input

elk
cow
bat
*
ea
acm+e
nm+o|jk+l
**
debian
slackware
gentoo
ubuntu
suse
fedora
mepis
*
yts
cab-e+n
r-e|zjq|i+t|vs-p+e-u-c
**
#

Expected output

bat
NONE
elk
$
gentoo
ubuntu
NONE
$

Example 2
Input
```
apple
*
a
**
#
```
Expected output
```
apple
$
```
Example 3
Input
```
cat
dog
cot
*
o-d
c
**
#
```
Expected output
```
cot
cat
$
```
Example 4
Input
```
xyz
abc
*
q|a
**
#
```
Expected output
```
abc
$
```
Example 5
Input
```
abc
abd
*
a+z
**
#
```
Expected output
```
NONE
$
```
Example 6
Input
```
b
a
*
a
**
zz
yy
*
y
**
#
```
Expected output
```
a
$
yy
$
```

Example 7

Input

programming
algorithm
structure
*
pa+r+g
s-a
**
#

Expected output

algorithm
structure
$