Permutations of a String

Marlow Locks ships combination padlocks whose code is a rearrangement of the letters printed on the barrel. Every letter on a barrel is different, and a valid code uses each of them exactly once. The recovery sheet packed with the lock lists every code the owner could possibly have set, in dictionary order so a customer can scan down it.

Task: Print every arrangement of the letters, one per line, in dictionary order.

Input

A single line holding between 1 and 8 lowercase letters, no spaces. All the letters are different. They do not necessarily arrive in alphabetical order.

Output

One arrangement per line, each using every letter of the input exactly once. Every possible arrangement must appear, none twice. Lines come out in dictionary order — the order they would appear in a word list, so abc before acb before bac.

Example:

Input:
abc

Output:
abc
acb
bac
bca
cab
cba