Given a string consisting of m symbols. Print all permutations of symbols for this string.

Input

One string consisting of m (2 ≤ m ≤ 8) of symbols - Latin letters and digits.

Output

Print all permutations for the given string in lexicographical order.