Unique Permutations of a String

Given a string \(s\), output all unique permutations of its characters. The permutations should be listed in lexicographical order. Note that the input string may contain duplicate characters, and in such cases, duplicate permutations should not be printed.

For example, if \(s = \texttt{aab}\), the unique permutations in lexicographical order are:

aab
aba
aab

However, after removing duplicates and sorting, the correct output is:

aab
aba
aa

More formally, if \(P(s)\) denotes the set of unique permutations of \(s\), you are required to print every element \(p \in P(s)\) on a new line, where the ordering satisfies \(p_1 \leq p_2 \leq \dots \leq p_k\) in lexicographical order.

inputFormat

The input consists of a single line containing the string \(s\). The string can be empty or consist of up to 100 characters.

outputFormat

Output each unique permutation of the string \(s\) in lexicographical order, one per line. If the string is empty, output an empty line.

## sample

abc

abc
acb
bac
bca
cab
cba

</p>