Lexicographically Sorted Permutations

Given a string s, your task is to generate all of its permutations in lexicographically sorted order. Each permutation should be printed on a separate line.

Note: The string will consist of distinct characters.

For example, for the input s = "abc", the expected output is:

abc
acb
bac
bca
cab
cba

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output all permutations of the string s in lexicographically sorted order. Each permutation should be printed on a new line.

a

a