You are given a string $$$s$$$ consisting of pairwise distinct lowercase English letters.
Your task is to generate all possible permutations of the characters in the string and output them in lexicographical order.
The only line contains a string $$$s$$$ $$$(1 \le |s| \le 8)$$$ consisting of lowercase English letters. All characters in $$$s$$$ are pairwise distinct.
Print all permutations of the string $$$s$$$ in lexicographical order, each on a new line.
Input:
abc
Output:
abc acb bac bca cab cba