406352: GYM102386 I Персеантовка

I. Персеантовкаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный выводИезвтсен факт, что елси имзнеить продяок бкув вунрти солва, члевоек всё ранво сомежт пноять сымсл тескта, елси превая и полсендяя бувка осатунтся на метсе.

Вам дан текст. Текст — это строка, состоящая из строчных латинских букв и пробелов, завершающаяся точкой. Словом называется непустая строка, состоящая из строчных латинских букв, такая, что перед первой буквой слова находится начало текста или пробел, а после последней буквы слова находится точка или пробел. Гарантируется, что между каждой парой соседних слов стоит ровно один пробел. Гарантируется, что точка в тексте содержится ровно одна. Она следует строго за последним словом. Пробела между последним словом и точкой быть не может. Гарантируется, что в тексте есть по крайней мере одно слово.

В тексте авторы переставили некоторые буквы внутри слов местами, при этом не изменяя первую и последнюю букву слов. У вас имеется словарь всех возможных слов, которые могли встречаться в тексте до того, как буквы были переставлены. Никакие другие слова не могли встречаться в исходном тексте. Ваша задача — написать программу, которая сможет восстановить исходный текст (то, каким он был до перестановки букв).

Входные данные

В первой строке вводится текст, полученный после некоторой перестановки символов некоторых слов. Гарантируется, что суммарная длина текста не превышает $$$5\cdot 10^5$$$ символов.

В следующей строке вводится целое число $$$n$$$ — количество слов в словаре $$$(1\leq n\leq 5\cdot 10^5)$$$.

Каждая из следующих $$$n$$$ строк содержит одно слово из словаря. Гарантируется, что суммарная длина всех слов в словаре не превышает $$$5\cdot 10^5$$$ символов. Также гарантируется, что все слова в словаре различны.

Выходные данные

Выведите единственную строку — исходный текст до перестановки символов. Если существует несколько возможных вариантов ответа, выведите любой из них. Если не существует ни одного корректного варианта ответа, выведите «No solution» (без кавычек).

ПримерыВходные данные

hello wolrd.
2
hello
world

Выходные данные

hello world.

Входные данные

hello wlrd.
2
hello
world

Выходные данные

No solution

Входные данные

tihs is vrey sceret txet.
7
text
secret
serect
scret
is
very
this

Выходные данные

this is very secret text.