All Permutations

Lab Python Advanced 30 points

Read a word with distinct letters and print all its permutations in alphabetical order, generated recursively (not with itertools).

Input

One word (≤ 6 letters).

Output

One permutation per line.

Example

Input

abc

Output

abc
acb
bac
bca
cab
cba

Sample input available Sample output available

Editor

Python

Hints

Pick each letter as the first one, then permute the remaining letters.

Solution explanation

The recursion tree has n! leaves, so this is only practical for short words.

Show solution

def permutations(s):
    if len(s) <= 1:
        return [s]
    result = []
    for i, ch in enumerate(s):
        for rest in permutations(s[:i] + s[i + 1:]):
            result.append(ch + rest)
    return result


print("\n".join(sorted(permutations(input()))))

Output

Answer