Team ID Generation

You are given a string s containing a set of characters. Your task is to generate all unique permutations of the string in lexicographical order.

For a string of length n, there are at most \( n! \) possible permutations. However, if some characters are repeated, duplicate permutations must be removed.

For example, if \( s = "ABC" \), then the unique permutations are:

ABC
ACB
BAC
BCA
CAB
CBA

Input will be provided via standard input and output via standard output. Make sure your code reads from stdin and writes the answer to stdout.

inputFormat

Input consists of a single line containing the string s. The string will consist of uppercase English letters only.

outputFormat

Output all unique permutations of the string in lexicographical order, each on a separate line.

## sample

ABC

ABC
ACB
BAC
BCA
CAB
CBA

</p>