Spell Check
The University of Magic Kurufinwe in Alkarinqwe is renowned as one of the most powerful magical institutions in the elven land of Laurelin. Currently, the Archmages there are on the verge of deciphering the ancient language of magical elementals, Qwen'Iaur. They have compiled a list of all the words in this language, but not every combination of these words results in a functional spell.
Fortunately, the Archmages discovered an ancient artifact called Sarandol, also known as the Oracle, deep within their castle's dungeons. According to legend, this artifact can create functional spells! However, it was crafted by the legendary mage Beligur the Great and is protected by a unique mechanism. The Oracle produces a spell as a continuous string without spaces, which can only be interpreted as an alphabetical string S of length L. This presents the first challenge. The second challenge is that the artifact sometimes generates sequences that cannot be formed from the words of the Qwen'Iaur language. In other words, there might not be a sequence of words α_1, α_2, ..., α_k such that S = α_1α_2...α_k, where each word α_i is found in the Qwen’Iaur language (words can be reused). If at least one such sequence exists, it indicates that the Oracle has produced a string that is a functional spell.
Your task is to develop a magical program for your magical computer to determine if at least one such sequence exists.
Input
The first line contains the number of words n (1 ≤ n ≤ 1000) in the dictionary. The next n lines contain the words of the Qwen'Iaur language. The final line is the string S, generated by Sarandol. All dictionary words are no longer than 100 characters, and L ≤ 10000. Words and strings are case-insensitive and consist only of English letters and the symbols ’ and ‘ (with ASCII codes 39 and 96).
Output
If the string can be interpreted as a functional spell, output YES; otherwise, output NO.