eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Проверка заклинаний

Проверка заклинаний

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 256 MiB

Университет магии 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.

Приклад

Вхідні дані #1
4
all
bar
Akh
kar
bakarkarbar
Вихідні дані #1
NO
Джерело 2012 Харьков, Зимняя школа, День Сергея Копеловича, Задача K