B

B. Шпаргалка

Вася готовится к экзамену по алгоритмам и на всякий случай пишет шпаргалки.

Чтобы уместить на них как можно больше информации, он не разделяет слова пробелами. В итоге получается одна очень длинная строка. Чтобы на самом экзамене из-за нервов не запутаться в прочитанном, он просит вас написать программу, которая по этой длинной строке и набору допустимых слов определит, можно ли разбить текст на отдельные слова из набора.

Более формально: дан текст T и набор строк s₁, ... ,s_n. Надо определить, представим ли T как s_k1s_k2...s_kn, где где k_i — индексы строк. Индексы могут повторяться. Строка s_i может встречаться в разбиении текста T произвольное число раз. Можно использовать не все строки для разбиения. Строки могут идти в любом порядке.

Формат ввода

В первой строке дан текст T, который надо разбить на слова. Длина T не превосходит 10⁵. Текст состоит из строчных букв английского алфавита. Во второй строке записано число допустимых к использованию слов 1 ≤ n ≤ 100.

В последующих n строках даны сами слова, состоящие из маленьких латинских букв. Длина каждого слова не превосходит 100.

Формат вывода

Выведите «YES», если текст можно разбить на слова из данного словаря, или «NO» в ином случае.

Пример 1

examiwillpasstheexam 5 will pass the exam i

YES

Пример 2

abacaba 2 abac caba

NO

Пример 3

abacaba 3 abac caba aba

YES