Description

Given a string consisting of distinct lowercase letters, output all possible permutations of the string. We assume that the lowercase letters follow the order 'a' < 'b' < ... < 'y' < 'z', and the given string is already sorted in ascending order.

Input Format

Only one line of input is provided, containing a string composed of distinct lowercase letters. It is known that the length of the string is between 1 and 6.

Output Format

Output all permutations of the string, one permutation per line. The permutations should be ordered lexicographically from smallest to largest.

Lexicographical order is defined as follows:
Given $S = s_1s_2...s_k$ and $T = t_1t_2...t_k$,
$S < T$ if and only if there exists a position $p$ ($1 \leq p \leq k$) such that $s_1 = t_1$, $s_2 = t_2$, ..., $s_{p-1} = t_{p-1}$, and $s_p < t_p$.

abc

abc
acb
bac
bca
cab
cba

Hint

This problem prohibits the use of STL and includes any related calls that can be utilized.