Unique Permutations Generator

Given a string ( s ) of length ( n ), your task is to generate all the unique permutations of ( s ). A permutation is an arrangement of all the characters of ( s ) in some order. Note that if ( s ) contains duplicate characters, some permutations might be the same. Your solution should output the unique permutations sorted in lexicographical order.

For example, if ( s = \texttt{abc} ), then all unique permutations are:

( abc, acb, bac, bca, cab, cba ).

If ( s = \texttt{aab} ), the unique permutations are:

( aab, aba, baa ).

You are required to read the input from the standard input (stdin) and output the result to the standard output (stdout).

inputFormat

The input consists of a single line containing the string ( s ). The string may contain duplicate characters. The length of ( s ) is at least 0 and reasonably small.

outputFormat

Output all the unique permutations of the input string sorted in lexicographical order. Each permutation should be printed on a separate line. If the input string is empty, output an empty line.## sample

abc

abc
acb
bac
bca
cab
cba