Word Concatenation Challenge

You are given a string s consisting of lowercase Latin letters and a dictionary of words. Your task is to determine whether it is possible to form the string s by concatenating one or more words from the dictionary. Each word in the dictionary can be used any number of times.

More formally, let \( s \) be a string and let \( D \) be a set of words. Determine if there exists a sequence of words \( w_1, w_2, \dots, w_k \) (with \( w_i \in D \)) such that:

[ s = w_1 w_2 \dots w_k ]

If such a sequence exists, print YES; otherwise, print NO.

Note: The words can be repeated and concatenated in any order.

inputFormat

The input is read from stdin and has the following format:

T
s_1
n_1
word_1
word_2
... 
word_{n_1}
s_2
n_2
word_1
word_2
... 
word_{n_2}
...
s_T
n_T
word_1
word_2
... 
word_{n_T}

Where:

• T is the number of test cases.
• For each test case, s is the target string.
• n is the number of words in the dictionary.
• The subsequent n lines each contain one dictionary word.

outputFormat

For each test case, output a single line to stdout containing either YES if the string can be formed by concatenating the dictionary words, or NO otherwise.

## sample

3
applepenapple
3
apple
pen
applepen
catsandog
5
cats
dog
sand
and
cat
pineapplepenapple
4
apple
pen
pine
pineapple

YES
NO
YES

</p>