Frugal Search

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.

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.

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 ($).