1082 - 全排列V2
Description

给出一个字符串S(可能有重复的字符),按照字典序从小到大,输出S包括的字符组成的所有排列。例如:S = "131",

输出为:

113
131
311


Input
输入一个字符串S(S的长度 <= 9,且只包括0 - 9的阿拉伯数字)


Output
输出S所包含的字符组成的所有排列


Examples

Input

1312

Output

1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
题目参数
Time Limit 10 seconds
Memory Limit 128 MB
提交次数 57
通过次数 34