String Permutations

You are given a string s consisting of lowercase alphabetical characters. Your task is to generate and print all unique permutations of the string in lexicographical order.

Note that if the string contains duplicate characters, some permutations will be identical. In that case, only print the distinct permutations.

The total number of distinct permutations of a multiset of n characters with frequencies \(f_1, f_2, \ldots, f_k\) is given by the formula:

[ \frac{n!}{f_1!,f_2!,\cdots,f_k!} ]

Example: For the input string "aab", the distinct permutations are:

• "aab"
• "aba"
• "baa"

inputFormat

The input consists of a single line containing the string s (with at most 100 characters) consisting only of lowercase alphabetical characters.

outputFormat

Print all distinct permutations of s in lexicographical order. Each permutation should be printed on a new line.

## sample

a

a

</p>