Expand Sentence with Synonyms

You are given a sentence and a dictionary of synonyms. For each word in the sentence that exists in the dictionary, you may replace it with any of its synonyms (including the original word). Your task is to generate all possible sentences by replacing each word with one from its list (if available).

Formally, let the sentence be a sequence of words \(w_1, w_2, \dots, w_m\). For each word \(w_i\) that is a key in the dictionary \(D\), let its options be \(\{w_i\} \cup D(w_i)\). The output should list all sentences formed by selecting one option for each word. Use the product of these options.

Note: The replacement options for a word always include the word itself.

inputFormat

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

• The first line contains the original sentence.
• The second line contains an integer \(N\) representing the number of dictionary entries.
• The next \(N\) lines each describe a dictionary entry. Each line starts with a word (the key), followed by an integer \(k\) indicating the number of synonyms, followed by \(k\) synonyms separated by spaces.

outputFormat

The program should output to standard output (stdout) the list of all possible sentences. Each sentence should be printed on a new line. The order of sentences must follow the natural order of generating the Cartesian product based on the input order.

## sample

I like apples
2
like 2 love enjoy
apples 2 fruits oranges

I like apples
I like fruits
I like oranges
I love apples
I love fruits
I love oranges
I enjoy apples
I enjoy fruits
I enjoy oranges

</p>