Lexicographical Permutations

Given a string S, generate all the permutations of its characters and output them in lexicographical order.

Each permutation should be printed on a new line.

For example, if the input is abc, then the output should be:

abc
acb
bac
bca
cab
cba

Your solution should read the input from stdin and write the output to stdout.

inputFormat

The input consists of a single line containing the string S. It is guaranteed that S contains only characters without spaces.

outputFormat

Output all the permutations of the string S in lexicographical order. Each permutation must be printed on its own line.

## sample

abc

abc
acb
bac
bca
cab
cba

</p>