Unique String Permutations

Given a string ( s ) consisting of characters (which may include duplicates), your task is to compute all unique permutations of ( s ) such that each permutation contains the characters in a different order. The output should be all the unique permutations sorted in lexicographical order, with each permutation printed on a separate line.

For example, if ( s = \texttt{abc} ), then the output should be:
abc
acb
bac
bca
cab
cba

When all characters in ( s ) are distinct, the total number of permutations is ( n! = 1 \times 2 \times \cdots \times n ). In the case of duplicate characters, duplicate permutations must be eliminated. If the input string is empty, output an empty line.

inputFormat

A single line containing the string ( s ). The string consists of lowercase letters (or may be empty) and has a maximum length of 10.

outputFormat

Print all unique permutations of the input string ( s ) in lexicographical order, each on a separate line.## sample

abc

abc
acb
bac
bca
cab
cba