Lexicographically Sorted Permutations

Given a string S, generate all possible permutations of its characters in lexicographically sorted order. For example, if S = "ABC", the output should be:

ABC
ACB
BAC
BCA
CAB
CBA

Note that the permutations are sorted in lexicographical (dictionary) order. In mathematical terms, if P denotes the set of all permutations of S, then:

\( P = \{ p(S) : p \text{ is a permutation of } S \} \)

and the output should list the elements of \( P \) in increasing order.

inputFormat

The input consists of a single string S (with no spaces) read from stdin.

outputFormat

Output all the lexicographically sorted permutations of S, each on a new line, to stdout.

## sample

ABC

ABC
ACB
BAC
BCA
CAB
CBA

</p>