Word Break Problem

You are given a string \( s \) and a dictionary of words. Your task is to determine if \( s \) can be segmented into a sequence of one or more dictionary words. If such a segmentation exists, output one valid segmentation (words separated by a single space). Otherwise, output IMPOSSIBLE.

Note: If there exist multiple valid segmentations, you may output any one of them.

Example:

• For \( s = \texttt{applepenapple} \) and dictionary = {\( \texttt{apple}, \texttt{pen}, \texttt{pine} \)}, one correct answer is apple pen apple.
• For \( s = \texttt{applepie} \) and dictionary = {\( \texttt{apple}, \texttt{pen} \)}, the answer is IMPOSSIBLE.

The segmentation is determined using standard dynamic programming techniques.

inputFormat

The input is given via standard input.

The first line contains an integer \( T \) (\( 1 \le T \le 100 \)), the number of test cases. Then, for each test case, the input format is as follows:

1. A line containing the string \( s \) which consists of lowercase letters.
2. A line containing an integer \( n \) (the number of words in the dictionary).
3. Then \( n \) lines follow, each containing a word that belongs to the dictionary.

It is guaranteed that the sum of the lengths of \( s \) over all test cases does not exceed \( 10^5 \).

outputFormat

For each test case, print a single line containing a valid segmentation of the string \( s \) using the dictionary words. Words in the segmentation should be separated by a single space. If it is not possible to segment \( s \) as required, output IMPOSSIBLE.

## sample

3
applepenapple
3
apple
pen
pine
catsanddog
4
cats
dog
sand
and
applepie
2
apple
pen

apple pen apple
cats and dog
IMPOSSIBLE

</p>