Word Segmentation

Given a dictionary of words and a set of test strings, determine whether each test string can be segmented into a space-separated sequence of one or more dictionary words. The problem can be approached using dynamic programming with the recurrence relation: $$dp[i] = \bigvee_{0 \le j < i} (dp[j] \land (s[j:i] \in \text{dict}))$$ where $$s[j:i]$$ represents the substring from index (j) to (i-1). Output "YES" if the string can be segmented, otherwise output "NO".

inputFormat

Input is read from standard input (stdin). The first line contains a positive integer (T), the number of test cases. For each test case, the first line contains a positive integer (N) representing the number of words in the dictionary, followed by (N) space-separated words. The next line contains a positive integer (M) representing the number of test strings, followed by (M) lines, each containing a test string.

outputFormat

For each test case, output (M) lines to standard output (stdout). Each line should contain "YES" if the corresponding test string can be segmented into dictionary words, or "NO" otherwise.## sample

1
5
apple pen applepen pine pineapple
3
applepenapple
pineapplepenapple
catsandog

YES
YES
NO