В некоторых IDE поддерживается навигация по файлам через их сокращённые названия. Если в языке принято называть классы CamelCase'ом (как в Java, например), то по заглавным буквам названия можно быстро найти нужный класс. Например, если название класса «MyFavouriteConfigurableScannerFactory», то его можно найти по строке «MFCSF». Но если в проекте есть класс «theMultiFunctionalCommaSeparatedFile», то он тоже будет подходить под этот паттерн, и при поиске надо будет выбрать между этими двумя вариантами.
Вам дан набор строк в CamelCase. Далее будут поступать запросы в виде строк-паттернов из прописных букв английского алфавита. Вам надо находить такие строки среди исходных, которые удовлетворяют заданному шаблону, и выводить их в лексикографическом порядке.
Также в паттерне может быть только несколько первых заглавных букв. Например, если бы в указанном выше примере был бы паттерн «MFCS», то существующие две строки походили бы под него, а также подходил бы, например, «MamaFicusCodingSouthWestNorth». А вот «MamaCodingSouthWestNorth» –— уже нет.
В первой строке записано число — количество названий классов в исходном наборе n (1 ≤ n ≤ 105). Все названия состоят из строчных и прописных букв английского алфавита.
В следующих n строках даны сами названия по одному в строке. Суммарная длина этих строк не превосходит 107.
Затем дано количество запросов m (1 ≤ m ≤ 100).
В следующих m строках даны сами запросы. Каждый запрос –— это шаблон, строка из прописных букв английского алфавита, в длину не превышающая 105. Шаблон может быть пустым. Заметьте: шаблону из нуля прописных букв удовлетворяет любое название.
Для каждого отдельного запроса (в порядке их поступления) выведите в лексикографическом порядке все строки, которые подходят под данный шаблон. Если какие-то строки одинаковые, то выведите все экземпляры. Если ни одна из строк не подходит под шаблон, то выведите для данного запроса пустую строку.
|
3 MamaMilaRamu MamaMia MonAmi 2 MM MA |
MamaMia MamaMilaRamu MonAmi |
|
2 AlphaBetaGgamma AbcdBcdGggg 2 ABGG ABG |
AbcdBcdGggg AlphaBetaGgamma |
|
5 WudHnagkbhfwrbci WCUkvoxboxufsdap jdrxomezzrpuhbgi ZcGHdrPplfoldemu cylbtqwuxhiveznc 3 WGHV NKVDT ZGHU |