Unique Permutations

Given a string s, your task is to generate all unique permutations of its characters. The resulting permutations must be sorted in lexicographical (alphabetical) order.

If the input is an empty string, the output should be a single empty line representing the empty permutation.

You may find the formula for the number of distinct permutations useful. In general, for a string with characters having frequencies \(n_1, n_2, \ldots, n_k\), the number of unique permutations is given by:

[ \frac{n!}{n_1!, n_2!, \cdots \ n_k!} ]

inputFormat

The input consists of a single line containing a string s which may include repeated characters. The string can be empty.

outputFormat

Output all unique permutations of the input string, each on a separate line, sorted in lexicographical order.

## sample

cat

act
atc
cat
cta
tac
tca

</p>