Пошуки скарбів

Одного разу Лосяш знайшов старовинний манускрипт, який містив карту шдяхе до старовинної печери, в якій лежали скарби далеких предків Смішариків. Всім відомо, що стародавні Смішарики були високоінтелектуальною народністю, тому двері до печери були захищені паролем. У древньому манускрипті містилась інформація про те, як підібрати пароль. У стародавніх Смішариків було магічне заклинання, яке вони використовували для виклику злих духів. На дверях до печери було вибито багато точечок, які були з'єднані стрілочками. Над кожною стрілочкою була написана ряжкова літера латинського алфавіту. Давнє пророцтво гласило, що пароль можна отримати, пройшовши по стрілочкам від деякої конкретної точечки (чарівної) до якоїсь іншої. Більше того, Лосяш вияснив, що пароль міститься в магічних заклинаннях для виклику злих духів як підрядок рівно k разів. Допоможіть Лосяшу знайти пароль і відкрити світу скарби стародавної народності Смішариків. Якщо варіантів паролю, що відповідають даним умовам, декілька, то згодиться довільний. Також врахуйте, що манускрипт Лосяшу могли підкинути вороги. У такому випадку пароля не існує.

Вхідні дані

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

Початковою чарівною точкою є точка з номером 1. Всі точки нумеруються з одиниці.

Вихідні дані

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

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

• не можна вивести пароль X, якщо в списку виведених паролів є інший пароль, для якого X є префіксом.

Якщо паролей не існує, то вихідний файл містить пустий рядок. Гарантується, що довжина вихідного файлу не превищує 120000 символів.