Permutations

Problem Background

Special for beginners, ^_^

Problem Description

Given a string consisting of distinct lowercase letters, output all permutations of this string. We assume that for lowercase letters $a < b < \dots < y < z$, and that the letters in the given string are already sorted in ascending order.

Input Format

The input is a single line, a string consisting of distinct lowercase letters, whose length is known to be between 1 and 6.

Output Format

Output all permutations of this string, one per line, in lexicographic order (smaller permutations first). Lexicographic order is defined as follows:

Given $S = s_1s_2\dots s_k, T = t_1t_2\dots t_k$, then $S < T$ means that there exists $p\;(1 \le p \le k)$ such that $s_1 = t_1, s_2 = t_2, \dots, s_{p-1} = t_{p-1}, s_p < t_p$ holds.

Sample Input

abc

Sample Output

abc
acb
bac
bca
cab
cba

Constraints

Time limit: 1s, memory limit: 1024KiB for each test case.