Lexicographical Permutations

Given a string s, your task is to generate all distinct permutations of s in lexicographical (dictionary) order.

For example, for the string abc the lexicographical order of permutations is:

\(abc, acb, bac, bca, cab, cba\)

If the string contains duplicate characters, only distinct permutations should be printed. For example, for the input baa, the correct output is:

\(aab, aba, baa\)

Input Format: A single line containing the string s.

Output Format: Print each permutation in a new line in lexicographical order.

inputFormat

The input consists of a single line containing the string s (which may include duplicate characters or even be empty).

outputFormat

Output each unique permutation of the input string in lexicographical order, each on a separate line. If the input string is empty, output an empty line.

## sample

abc

abc
acb
bac
bca
cab
cba

</p>