Unique Lexicographical Permutations

Given a string \( S \), your task is to generate all unique permutations of \( S \) and output them in lexicographical order. The string \( S \) can include uppercase letters, digits, and special characters. Each permutation should be printed on a separate line.

Note: The lexicographical order is defined based on the ASCII values of characters. For example, if \( S = "A1B" \), the output should be:

1AB
1BA
A1B
AB1
B1A
BA1

The expected time complexity for generating the next permutation is \( O(n) \) per permutation.

inputFormat

The input consists of a single line containing the string \( S \).

outputFormat

Output all unique permutations of \( S \) in lexicographical order. Each permutation should be printed on a new line.

## sample

ABC

ABC
ACB
BAC
BCA
CAB
CBA

</p>