Generate permutations

Given a string with unique characters s, you are asked to print all the possible |s|! permutations of the string.

Input

The input contains a single line representing s (1 ≤ |s| ≤ 8). It’s guaranteed that all the letters are unique.

Output

The program should print all the possible permutations of s each on a separate line. They can be in arbitrary order.

Examples