All orders of tasks

Problem

A scheduler has n tasks, each named by a different lowercase letter. Print every order in which they can run, one per line, in dictionary order.

Example

Input

abc

Output

abc
acb
bac
bca
cab
cba

Six orders.

Try the problem first. Open one hint at a time.

Hint 1

Sort the letters first, then try them in that order at every position.

Hint 2

Keep a used flag for each letter. Set it when choosing and clear it when undoing.

Write your Python code, run it on the examples and submit it to hidden tests.