Word Break II

Given a non‐empty string \(s\) and a list of non-empty words (the word dictionary), your task is to determine all possible segmentations of \(s\) such that every segmented word is in the dictionary. In other words, split the string into a space-separated sequence of one or more dictionary words.

For example, for \(s = \texttt{catsanddog}\) and dictionary \(\{\texttt{cat}, \texttt{cats}, \texttt{and}, \texttt{sand}, \texttt{dog}\}\), the valid segmentations are "cat sand dog" and "cats and dog".

If no segmentation exists, output nothing. Note that for the empty string, the only valid segmentation is the empty string.

inputFormat

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

Line 1: A non-empty string \(s\).
Line 2: An integer \(n\) representing the number of words in the dictionary.
Next \(n\) lines: Each line contains a dictionary word.

For example:

catsanddog
5
cat
cats
and
sand
dog

outputFormat

Output all possible valid segmentations, one per line, to standard output. The order of the segmentation does not matter. If no segmentation exists, output nothing. For the empty string input, output a single empty line.

## sample

catsanddog
5
cat
cats
and
sand
dog

cat sand dog
cats and dog

</p>