Segment Comments

You are given a dictionary of words and a list of comments. For each comment, determine whether it can be segmented into one or more words found in the dictionary. The segmentation requires that the entire comment be segmented; partial segmentation is not allowed. You can use dynamic programming to solve this problem. More formally, given a string (s) and a dictionary (D), determine if there exists a sequence of indices (0 = i_0 < i_1 < \cdots < i_k = |s|) such that for each segment (s[i_{j-1}, i_j]) is in (D).

inputFormat

The first line contains an integer (n) representing the number of words in the dictionary. If (n > 0), the second line contains (n) space-separated words. The next line contains an integer (m) representing the number of comments to check. Then (m) lines follow, each containing a single comment string with no spaces.

outputFormat

For each comment, print a separate line with either "YES" if the comment can be segmented into dictionary words, or "NO" if it cannot.## sample

5
hello world apple pie cat
3
helloworld
applepie
applesauce

YES
YES
NO