The problem statement is simple. You are given a string and you are supposed to print all the distinct permutations of the string, as they would appear in an dictionary.

INPUT
The first and only line of the input contains a single string, S.

OUTPUT
The output contains the required strings, each string in a seperate line.

CONSTRAINTS
1<=|S|<=9