Lexicographically Sorted Permutations

You are given a string s. Your task is to generate all possible permutations of the characters in s and output these permutations in lexicographical (dictionary) order.

If the input string is empty, the output should be a single empty line representing the empty permutation.

For example, if s = \(ABC\), then the permutations in lexicographical order are:

\[ ABC,\; ACB,\; BAC,\; BCA,\; CAB,\; CBA \]

The solution must read input from standard input (stdin) and produce output to standard output (stdout), with each permutation printed on a new line.

inputFormat

The input consists of a single line containing the string s. The string may include letters, digits, or other characters. The length of s is not more than 1000 characters.

outputFormat

Output all the permutations of the string s in lexicographical order. Print each permutation on its own line. If the string is empty, output a single empty line.

## sample

ABC

ABC
ACB
BAC
BCA
CAB
CBA

</p>