Treasure hunt (RU)

Однажды Лосяш нашел древний манускрипт, содержащий карту пути к древней пещере, в которой лежали сокровища далёких предков Смешариков. Всем известно, что древние Смешарики были высокоинтеллектуальной народностью, поэтому дверь в пещеру была защищена паролем. В древнем манускрипте содержалась информация о том, как подобрать пароль. У древних Смешариков было магическое заклинание, которое они использовали для вызова злых духов. На двери в пещеру была выбита куча точечек, которые были соединены стрелочками. Над каждой стрелочкой была написана строчная буковка латинского алфавита. Древнее пророчество гласило, что пароль можно получить, пройдя по стрелочкам от некоторой конкретной точечки (волшебной) до какой-то другой. Более того, Лосяш выяснил, что пароль содержится в магическом заклинании для вызова злых духов как подстрока ровно k раз. Помогите Лосяшу найти пароль и открыть миру сокровища древней народности Смешариков. Если вариантов пароля, отвечающих данным условиям, несколько, то сгодится любой. Также учтите, что манускрипт Лосяшу могли подбросить враги. В этом случае пароля не существует.

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

На первой строке находится заклинание. Длина магического заклинания L ≤ 10⁵. На второй строчке находятся числа N и M (N, M ≤ 10⁵) – число точечек и число стрелочек. В следующих M строчках содержится информация о стрелочках: номер стартовой точечки, номер конечной точечки и строчная буковка латинского алфавита. На последней строчке содержится число k (1 ≤ k ≤ L). Внимательно анализируя картинку на двери в пещеру, Лосяш заметил, что количество различных путей из волшебной точечки в остальные не превышает 10⁵. Зато Лосяш обрадовался, что все переходы детерминированы, то есть из каждой по любому символу существует не более одного пути.

Начальной волшебной точкой является точка с номером 1. Все точки нумеруются с единицы.

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

Если пароли существуют, то Вы должны вывести в лексикографическом порядке все те из них, которые удовлетворяют следующим условиям:

• пароли выводятся по одному в строке;

• нельзя вывести пароль X, если в списке выведенных паролей есть другой пароль, для которого X является префиксом;

Если паролей не существует, то выходной файл содержит пустую строку. Гарантируется, что длина выходного файла не превышает 120000 символов.