Перевірка заклинань
Університет магії Kurufinwe в Alkarinqwe відомий як один з найсильніших університетів магії в країні ельфів Laurelin. Архімаги цього університету наблизилися до розгадки таємниці давньої мови магічних елементалів Qwen'Iaur. Вони вже мають список усіх слів цієї мови, але комбінації цих слів не завжди утворюють працююче заклинання.
На щастя, Архімаги знайшли в підземеллях свого замку давній артефакт Сарандол, також відомий як Оракул. Легенди стверджують, що цей артефакт здатний створювати працюючі заклинання! Проте він був створений одним із найвеличніших магів давнини Белігуром Великим і має особливий механізм захисту. Оракул видає заклинання у вигляді рядка без пробілів між словами, так що воно може бути прочитане лише як алфавітний рядок S довжини L. Але це лише перша проблема. Друга полягає в тому, що артефакт іноді генерує послідовності, які не можуть бути складені зі слів мови Qwen'Iaur, тобто не існує такої послідовності слів α_1, α_2, ..., α_k, що S = α_1α_2...α_k, де всі слова α_i присутні в мові Qwen’Iaur (одне й те саме слово може бути використане більше одного разу). Але якщо хоча б одне таке представлення існує, можна зробити висновок, що Оракул згенерував рядок, який є працюючим заклинанням.
Ваше завдання - написати магічну програму для вашого магічного комп'ютера, яка перевірить існування хоча б одного такого представлення.
Вхідні дані
У першому рядку міститься кількість слів n (1 ≤ n ≤ 1000) у словнику. n наступних рядків містять слова мови Qwen'Iaur. Останнім йде рядок S, згенерований Сарандолом. Усі слова у словнику мають довжину не більше 100 символів, L ≤ 10000. Слова і рядки не чутливі до регістру і можуть складатися тільки з англійських літер і двох символів ’ і ‘ (ці символи мають коди ASCII 39 і 96).
Вихідні дані
Якщо рядок може бути прочитаний як робоче заклинання, виведіть YES, інакше виведіть NO.