FRSEARCH - Frugal Search

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 +s ("positive" s) or -s ("negative" s), where s 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.

Input

The input consists of one or more test cases followed by a line containing only "#" that signals the end of the input. Each test case consists of 1-100 words, each on a line by itself, followed by a line containing only "*" 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 "**" that marks the end of the test case. Each word will consist of 1-20 lowercase letters. All words within a test case will be unique. Each query will be as defined above and will be 1-79 characters long.

Output

For each query, output a single line containing the lexicographically smallest word within that test case that matches the query, or the word NONE if there is no matching word. At the end of each test case, output a dollar sign on a line by itself.

Example

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
**
#

Output:
bat
NONE
elk
$
gentoo
ubuntu
NONE
$

Added by:Nikola P Borisov
Date:2008-10-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Mid-Central Regional ACM-ICPC Contest 2006

hide comments
2019-12-06 05:28:28
Partial is a really bad choice for such problem. I have no way of knowing whether getting 0 means my solution is not efficient enough, errs, crashes or perhaps it's the judge or input that has issues. I'd lean towards the latter, but because of the ambiguous responses I can't even verify that by submitting code crafted for the purpose.

In any case, until one of the ACd solvers resubmits and gets AC proving me wrong, be warned you might be wasting time attempting to solve this.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.