Lexicographical Permutations

Given a string ( s ), your task is to generate all distinct permutations of its characters and print them in lexicographical order. The input string may contain letters, digits, and special characters. Note that even if some characters are repeated, each distinct permutation should be printed exactly once.

For example, given ( s = \texttt{abc} ), the distinct permutations are: [ abc,\ acb,\ bac,\ bca,\ cab,\ cba ]

If the string is empty, output an empty line.

inputFormat

Input is provided via standard input (stdin) as a single line containing the string ( s ).

outputFormat

Print the distinct permutations of ( s ) in lexicographical order. Each permutation should be printed on a separate line. There should be no extra spaces or blank lines.## sample

abc

abc
acb
bac
bca
cab
cba