Word Segmentation with Lexicographical Order

You are given a string \(s\) and a dictionary of words. Your task is to segment \(s\) into a sequence of one or more dictionary words such that the concatenation of these words is exactly \(s\). If there are multiple valid segmentations, you should output the lexicographically smallest one (when compared as a list of words). If no segmentation exists, output NONE.

Dynamic Programming Idea: Let \(dp[i]\) represent the lexicographically smallest segmentation (as a list of words) for the prefix \(s[0 \ldots i-1]\). Then for every dictionary word \(w\) that can fit ending at \(i\) (i.e. if \(s[i-|w|\ldots i-1] = w\) and \(dp[i-|w|]\) exists), update \(dp[i]\) by comparing the new segmentation \(dp[i-|w|] + [w]\) with the current value of \(dp[i]\). Finally, \(dp[n]\) (with \(n\) being the length of \(s\)) is the needed answer.

Note: The dictionary is sorted in lexicographical order to ensure that the lexicographically smallest segmentation is chosen.

inputFormat

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

1. The first line contains an integer \(T\) representing the number of test cases.
2. For each test case:
   1. A line containing the string \(s\).
   2. A line containing an integer \(N\), the number of words in the dictionary.
   3. A line with \(N\) space-separated words, representing the dictionary.

outputFormat

For each test case, output the segmented words separated by a single space on a new line. If no valid segmentation exists, output NONE.

## sample

1
applepie
3
apple pie orange

apple pie

</p>