Description

输入n（≤10）个小写字母（可能重复），输出n个字符的全部排列

Format

Input

第1行：1个小写字母字符串。

Output

若干行，每行1个排列。按字典序输出。

Samples

abaab

1:aaabb
2:aabab
3:aabba
4:abaab
5:ababa
6:abbaa
7:baaab
8:baaba
9:babaa
10:bbaaa