Word Break II

Given a non‐empty string \( s \) composed of lowercase English letters and a dictionary of words, your task is to insert spaces into \( s \) so that each segmented word is a valid dictionary word.

Return all possible sentences that can be formed by inserting spaces into \( s \) such that every word is in the dictionary. The order of the words in the sentence must follow their original order in \( s \). In case there is no valid segmentation, output nothing.

Note: When \( s \) is empty, consider that it forms a valid segmentation resulting in an empty sentence.

Example:

Input:
  s = "catsanddog"
  wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
cat sand dog
cats and dog

</p>

inputFormat

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

• The first line contains the string \( s \).
• The second line contains an integer \( n \), the number of words in the dictionary.
• This is followed by \( n \) lines, each containing a dictionary word.

outputFormat

Print each valid sentence on a new line to stdout. The sentences should be sorted in lexicographical order. If no valid segmentation exists, output nothing. In the special case where \( s \) is empty, output a single empty line.

## sample

catsanddog
5
cat
cats
and
sand
dog

cat sand dog
cats and dog

</p>