Суфіксний кулемет
_Або залік, або автомат.___________________
Ганнібал Ректор
Теоретична підготовка новобранців армії Поссілтума включала до себе не лише заняття з військового правознавства, але й початків криптографії. Лекції читав майор Мега Байт, з притаманим солдатським гумором. Гвідо та Нунціо, у завдання яких входив розвал армії Поссілтума зсередини, вирішили цим скористатись, внесши плутаницю у термінологію. На початку чергової лекції Нунціо підняв руку і запитав:
- Ось ви на попередній лекції розповідали про кінцеві автомати. А про кінцеві кулемети можете розповісти?
Мега Байт не розгубився.
- Суфіксний кулемет - це кінечний автомат, який приймає усі суфікси заданого рядка (ві нульового до L-го включно, де L - довжина рядка), і лише їх. Сержант Гвідо!
- Я, пане майор!
- Ви зможете відрізнити автомат від кулемета?
- Так точно, пане майор!
- Вам задано кінечний автомат. Потрібно перевірити, чи є він суфіксним кулеметом заданого рядка.
На жаль, написання програм такого типу не входило у обов'язки Гвідо та Нунціо як у Синдикаті, так і в корпорації М.І.Ф. Так що відповідну програму доведеться писати Вам.
Вхідні дані
У вхідному файлі задано один чи декілька тестових наборів. У першому рядку кожного набору задано кількість станів автомату N, кількість переходів M, а також кількість приймаючих станів T (1 ≤ T ≤ N ≤ 50000, 1 ≤ M ≤ 100000). У другому рядку через пропуск задано T різних чисел в межах від 1 до N - приймаючі стани автомату, у зростаючому порядку. У наступних M рядках задано переходи у вигляді a_i b_i c_i, де 1 ≤ a_i, b_i ≤ n, а c_i - маленька літера латинського алфавіту. Перехід відбувається зі стану a_i у стан b_i по літері c_i. Із кожного стану a_i є не більше одного переходу по символу c_i. Останній рядок опису набору - це рядок S, для якого автомат повинен бути кулеметом. Він складається лише з маленьких латинських літер, і довжина цого лежить в межах від 1 до 50000 включно. Крім того, сума усіх N та сумарна довжина усіх рядків, для яких необхідно здійснити перевірку, не перевищує 50000, а сума усіх M не перевищує 100000.
Файл завершується фіктивним набором, у якому N=M=T=0.
Початковим станом автомату є перший. Якщо при інтерпретації якогось рядкаи в автоматі відсутній відповідний перехід, то автомат вивалюється з помилкою і рядок не приймає. Таким чином, рядок приймається, лише якщо при його інтерпретації було знайдено усі переходи, і по їх завершенню автомат виявився у приймаючому стані (при цьому неважливо, були на шляху приймаючі стани, чи ні).
Вихідні дані
Виведіть у вихідний файл, чи є заданий автомат кулеметом, слідуючи формату приклада.