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