Задача №112557. Игра со словами
Девочка Катя любит разные игры со словами. Недавно она придумала новую игру. Увидев где-либо написанное слово, она пытается придумать предложение, содержащее это слово в себе. Буквы увиденного слова должны идти в предложении по порядку, но не обязательно подряд. Например, увидев слово "LTIBE", она придумывает предложение "LET IT BE". Разумеется, Катя ищет кратчайшее предложение.
Ваша задача помочь Кате, автоматизировав игру.
В первой строке содержится увиденное Катей слово. Слово состоит из заглавных латинских букв. Его длина не менее 1 символа и не более 500. Во второй строке входного файла записано целое число N (1 ≤ N ≤ 500) — количество слов в словарном запасе Кати. Далее в N строках записаны слова. Слова состоят из заглавных латинских букв, содержат не менее 1 и не более 50 букв. Слова в наборе могут совпадать. В искомом предложении слово может использоваться любое количество раз, главное, чтобы оно содержалось в списке.
Выведите искомое предложение. Слова в предложении разделяйте пробелами. Длиной предложения называется количество символов (включая пробелы) использующихся при его записи. Переведите в нижний регистр те символы, которые образуют заданное слово. Если решений несколько, выведите любое. Если решения не существует, выведите в выходной файл символ "*".
LTIBE 5 IT THE LET BEE BE
lEt iT be