Unique Lexicographical Permutations

Given a string s, generate all distinct permutations of the characters in s and output them in lexicographical order. The permutations should be printed one per line. If the input string is empty, output a single empty line.

For example, if s = "aab", the distinct permutations are:

[ aab \quad aba \quad baa ]

Your task is to write a program that reads the input from standard input (stdin) and prints the correct output to standard output (stdout).

inputFormat

The input consists of a single line containing the string s which may include repeated characters. The input is read from standard input.

outputFormat

Print each distinct permutation of s on a separate line in lexicographical order. If s is empty, print an empty line.

## sample

abc

abc
acb
bac
bca
cab
cba

</p>