Məsələlər
Xəzinə axtarışı
Xəzinə axtarışı
\includegraphics{https://static.e-olymp.com/content/ed/ed6d61df0657104be11f1d3df70443d3d871a8c5.jpg}
Bir dəfə Losya Smeşariklərin uzaq əcdadlarının xəzinəsinin yerləşdiyi qədim mağaralara gedən yolun xəritəsi yerləşən qədim manuskript (qədim əl yazısı) tapdı. Hamıya məlumdur ki, qədim smeşariklər yüksək intellektli xalq idilər, ona görə də mağaranın qapısı parol ilə müdafiə olunurdu. Qədim manuskriptdə parolu necə seçmək haqqında informasiya var idi. Qədim Smeşariklərdə pis ruhları çağırmaq üçün onların istifadə etdiyi sehrli ovsunlar var idi. Mağaranın qapısında bir-biri ilə oxlarla birləşdirilmiş vurulub deşilmiş çoxlu nöqtələr var. Hər oxun üzərində latın əlifbasının kiçik hərfləri yazılmışdır. Qədim uzaqgörənlər bildirir ki, oxlar üzrə konkret bəzi nöqtələrdən(sehrli) hansısa digərinə keçməklə parolu almaq olar. Bundan əlavə, Losya aydınlaşdırdı ki, parol \textbf{k} sayda alt sətir kimi verilən və pis ruhları çağırmaq üçün olan sehrli ovsunlarda yerləşir. Losyaya parolu tapmaqda və qədim Smeşariklər xalqının xəzinə dünyasını açmaqda kömək edin. Əgər verilən şərtlərə cavab verən parolun variantları bir neçədirsə, onda onlardan ixtiyari biri yararlıdır. Həmçinin, nəzərə alın ki, Losyaya manuskripti düşmənlər ata bilərlər. Bu halda parol yoxdur.
\InputFile
Birinci sətirdə ovsunlar yerləşir. Sehrli ovsunun uzunluğu \textbf{L} ≤ \textbf{10^5}-dir. İkinci sətirdə nöqtələrin və oxların sayı olan\textbf{ N} və \textbf{M} (\textbf{N}, \textbf{M} ≤ \textbf{10^5}) ədədləri yerləşir. Sonrakı \textbf{M }sayda sətirdə oxlar haqqında məlumatlar yerləşir: Başlanğıc və son nöqtələrin nömrələri və latın əlifbasının kiçik hərfləri.
Sonuncu sətirdə \textbf{k} (\textbf{1} ≤\textbf{k} ≤ \textbf{L}) ədədi yerləşir. Mağaranın qapısının şəklini diqqətlə analiz edərək Losya duydu ki, sehrli nöqtələrdən digərlərinə gedən müxtəlif yolların sayı \textbf{10^5}-i aşmır. Əvəzində Losya sevindi ki, bütün keçidlər determikdir, başqa sözlə, hər birindən istənilən simvola birdən artıq yol yoxdur.
İlkin sehrli nöqtə \textbf{1 }nömrəli nöqtədir. Bütün nöqtələr tək rəqəmlə nömrələnir.
\OutputFile
Əgər parol mövcuddursa, onda Siz leksikoqrafik (lüğətdəki) ardıcıllıqla onlardan aşağıdakı şərtləri ödəyənlərin hamısını çıxışa verməlisiniz:
• Hər sətirdə bir parol verilir;
• Əgər çıxış parollarının siyahısında \textbf{X}-in önşəkilçi olduğu digər parol varsa, onda \textbf{X }parolunu vermək olmaz.
Əgər parol yoxdursa, onda çıxış faylında boş sətir yerləşir. Çıxış faylının uzunluğunun \textbf{120000} simvolu aşmadığına təminat verilir.
Giriş verilənləri #1
ssssabaabbsss 2 1 1 2 a 3
Çıxış verilənləri #1
a