String Segmentation using Dictionary Words

Given a string (s) and a list of dictionary words, segment (s) into a sequence of space-separated dictionary words such that all characters of (s) are used. If there exists a valid segmentation, output the segmented string; otherwise, output (\text{Not Possible}).

For example, if (s = \texttt{helloworld}) and the dictionary is ["hello", "world", "this", "is", "fun"], the output should be "hello world" because (s = \texttt{hello} + \texttt{world}). If no valid segmentation exists, print (\text{Not Possible}).

More formally, given a string (s) and a dictionary (D), find words (w_1, w_2, \ldots, w_n \in D) such that (s = w_1w_2\ldots w_n).

inputFormat

Input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each test case has the following format:

1. An integer (k) representing the number of dictionary words.
   
2. A line containing (k) space-separated words forming the dictionary.
   
3. A line containing the string (s) that needs to be segmented.

outputFormat

For each test case, print a single line to standard output (stdout) containing the segmented sequence of words separated by a space if a valid segmentation exists. Otherwise, print (\text{Not Possible}).## sample

5
5
hello world this is fun
helloworld
2
cats dogs
catsanddogs
4
apple pen pineapple grape
applepen
4
apple pen pineapple grape
applepenapple
3
break this into
breakitdown

hello world
Not Possible
Not Possible
apple pen apple
Not Possible