KMP

KMP is a string algorithm that searches for occurrences of a string as substrings of another string. The name of the algorithm comes from the first letters of the last names of its authors: Donald Knuth, James Hiram Morris, and Vaughan Pratt.

This problem has nothing to do with the algorithm. It is about the naming itself. There are N computer scientists in this world, numbered from 1 to N. The i-th computer scientist has a name $A_i$. A name consists of one or more words, separated by a single space. A word consists of one or more characters. The first character is an uppercase letter (A-Z), and the remaining characters are lowercase letters (a-z).

There are Q queries, and each query is a string S of uppercase letters. You must determine whether an algorithm named S can be authored by a subset of these N computer scientists. Suppose, for example, that Donald Knuth, James Hiram Morris, and Vaughan Pratt invented another algorithm. The first characters of all words in each computer scientist's name are {D, K} for Donald Knuth, {J, H, M} for James Hiram Morris, and {V, P} for Vaughan Pratt. Then the algorithm can be named by taking exactly one of those first characters from each name (within the chosen subset of the N computer scientists). For example, DJV, DHP, KHV, KMP, and KJP are all possible. Order does not matter, so names like PKH and VHK are also valid. However, KKMP and LHO are not valid in this example.

More formally, you must determine whether there is a sequence of integers $X_1, X_2, \cdots, X_{|S|}$ such that:

• $1 \le X_1, X_2, \cdots, X_{|S|} \le N$
• $X_i \ne X_j$ whenever $i \ne j$
• One of the words in $A_{X_i}$ starts with the character $S_i$

The input begins with two integers N Q (1 ≤ N ≤ 50, 1 ≤ Q ≤ 1000), the number of computer scientists and the number of queries. The next line contains N strings $A_i$, the name of the i-th computer scientist. The sum of the lengths of all $A_i$ is at most 106. The next Q lines contain a string S, the query to answer. The sum of the lengths of all S is at most 106. It is also guaranteed that $A_i$ and S satisfy the format given in the problem statement.

For each query, output “YES” on a line if an algorithm named S can be authored by a subset of the N computer scientists; otherwise, output “NO”.