Задачі
Frugal Search
Frugal Search
+
s
s
-
s
s
s
For this problem you will write a search engine that takes a query, searches a collection of words, and finds the lexicographically smallest word that matches the query (i.e., 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 ("positive" ) or ("negative" ), where is a single letter. All letters are lowercase, and no letter will appear more than once within a term. A query will not contain spaces. A term matches a word if the word contains at least one of the unsigned letters, all of the positive letters, and none of the negative letters; a query matches a word if at least one of its terms matches the word.
\InputFile
The input consists of one or more test cases followed by a line containing only "\textbf{#}" that signals the end of the input. Each test case consists of \textbf{1}--\textbf{100} words, each on a line by itself, followed by a line containing only "\textbf{*}" that marks the end of the word list, followed by one or more queries, each on a line by itself, followed by a line containing only "\textbf{**}" that marks the end of the test case. Each word will consist of \textbf{1}--\textbf{20} lowercase letters. All words within a test case will be unique. Each query will be as defined above and will be \textbf{1}--\textbf{79} characters long.
\OutputFile
For each query, output a single line containing the lexicographically smallest word within that test case that matches the query, or the word \textbf{NONE} if there is no matching word. At the end of each test case, output a dollar sign on a line by itself.
Вхідні дані #1
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 ** #
Вихідні дані #1
bat NONE elk $ gentoo ubuntu NONE $