Економний пошук#6056
Для цієї задачі вам потрібно створити пошукову систему, яка приймає запит, шукає в колекції слів і знаходить лексикографічно найменше слово, яке відповідає запиту (тобто слово, яке з'явилося б першим в англійському словнику). Запит — це послідовність одного або більше термінів, розділених одиничними вертикальними рисками (). Термін — це одна або більше літер, за якими слідує нуль або більше підписаних літер. Підписана літера — це або ("позитивна"), або ("негативна"), де — це одна літера. Усі літери є малими, і жодна літера не з'явиться більше одного разу в межах терміна. Запит не міститиме пробілів. Термін відповідає слову, якщо слово містить принаймні одну з непідписаних літер, усі позитивні літери та жодної з негативних літер; запит відповідає слову, якщо принаймні один з його термінів відповідає слову.
Вхід складається з одного або більше тестових випадків, за якими слідує рядок, що містить лише #, який сигналізує про кінець введення. Кожен тестовий випадок складається з – слів, кожне на окремому рядку, за якими слідує рядок, що містить лише *, який позначає кінець списку слів, за яким слідує один або більше запитів, кожен на окремому рядку, за якими слідує рядок, що містить лише **, який позначає кінець тестового випадку. Кожне слово складатиметься з – малих літер. Усі слова в межах тестового випадку будуть унікальними. Кожен запит буде визначений, як зазначено вище, і буде – символів завдовжки.
Для кожного запиту виведіть один рядок, що містить лексикографічно найменше слово в межах цього тестового випадку, яке відповідає запиту, або слово NONE, якщо немає відповідного слова. В кінці кожного тестового випадку виведіть знак долара на окремому рядку.
Приклад 1