Frugal Search
Для этой задачи вам нужно разработать поисковую систему, которая принимает запрос, ищет в коллекции слов и находит лексикографически наименьшее слово, соответствующее запросу (то есть слово, которое первым появится в английском словаре). Запрос представляет собой последовательность из одного или нескольких терминов, разделенных одиночными вертикальными чертами ("|"). Термин состоит из одной или нескольких букв, за которыми следуют ноль или более подписанных букв. Подписанная буква может быть либо положительной, либо отрицательной, где — это одна буква. Все буквы строчные, и ни одна буква не будет повторяться в пределах одного термина. Запрос не содержит пробелов. Термин соответствует слову, если слово содержит хотя бы одну из неподписанных букв, все положительные буквы и ни одной из отрицательных букв; запрос соответствует слову, если хотя бы один из его терминов соответствует слову.
Входные данные
Входные данные состоят из одного или нескольких тестов, за которыми следует строка, содержащая только "#", что сигнализирует об окончании ввода. Каждый тест состоит из 1–100 слов, каждое на отдельной строке, за которыми следует строка, содержащая только "*", которая отмечает конец списка слов, за которой следует один или несколько запросов, каждый на отдельной строке, за которыми следует строка, содержащая только "**", которая отмечает конец теста. Каждое слово будет состоять из 1–20 строчных букв. Все слова в пределах теста будут уникальными. Каждый запрос будет определен как выше и будет длиной 1–79 символов.
Выходные данные
Для каждого запроса выведите одну строку, содержащую лексикографически наименьшее слово в пределах этого теста, которое соответствует запросу, или слово NONE, если подходящего слова нет. В конце каждого теста выведите знак доллара на отдельной строке.