Lexicographical Permutations of a String

You are given a string S consisting of lowercase letters. Your task is to generate all distinct permutations of the string in lexicographical order and print each permutation on a new line.

For example, if the input string is abc, the distinct permutations in lexicographical order are:

[ abc,\ acb,\ bac,\ bca,\ cab,\ cba ]

Note: Two permutations are considered the same if they consist of the same sequence of characters. Duplicate characters in the input may lead to fewer unique permutations.

The formula for the number of distinct permutations of a string is given by:

[ \frac{n!}{n_1!, n_2!, \cdots, n_k!} ]

where \( n \) is the total number of characters and \( n_1, n_2, \ldots, n_k \) are the frequencies of each distinct character.

inputFormat

The input consists of a single line containing the string S (with at most 100 characters).

Input is provided via standard input (stdin).

outputFormat

Output all distinct permutations of the string in lexicographical order. Each permutation must be printed on its own line, via standard output (stdout).

## sample

abc

abc
acb
bac
bca
cab
cba

</p>