Unique Word Permutations

Given a string that consists of words separated by spaces, your task is to compute all unique permutations of the words. Each permutation should be represented as a single string with the words separated by a space.

If the input string is empty, output a single empty line.

The output should be printed in lexicographical order (i.e. sorted in dictionary order).

Note: The order of the permutations does not matter as long as they are sorted before output.

inputFormat

The input consists of a single line containing a string of words separated by spaces. The string may be empty or contain one or more words.

outputFormat

Output all the unique permutations of the words, each on a new line, in lexicographical order. If the input string is empty, print a single empty line.

## sample

cat dog

cat dog
dog cat

</p>