Distinct Permutations

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

A permutation is a rearrangement of the characters in the string. For instance, for the string "ab", the possible permutations are "ab" and "ba".

If the string contains duplicate characters, each unique permutation should appear only once. In the case of an empty string, the output should be an empty line.

You may use recursion, backtracking, or the next permutation algorithm to generate the solutions, ensuring optimal handling of duplicate characters.

The mathematical formula for the total number of distinct permutations when all characters are unique is given by: $$P(n)=n!$$

inputFormat

The input consists of a single line that contains the string S.

Note: The string may include uppercase and lowercase letters, digits, and special characters.

outputFormat

Output each distinct permutation of S on a separate line, in lexicographical order.

a

a