[HNOI2003]历史年份History

明天就要考近代史了，小明决定把需要背诵的历史事件按照发生年份从小到大抄在一张纸上。

可是，抄写时相邻两个年份之间没有分隔符。例如，年份 $1894$、$1911$、$1949$ 连在一起后，纸上写成了：

189419111949

这使小明十分苦恼，于是他准备编写一个程序，将这些年份还原成原来的形式。

由于这些年份按照时间顺序严格递增排列，因此还原后的数字序列也必须满足严格递增的要求。但仅满足这一条件时，序列 $1$、$89$、$419$、$111949$ 也符合要求。显然，最后一个年份不可能如此之大，因此小明要求在满足严格递增的前提下，使最后一个数字尽可能小。

在最后一个数字最小的前提下，使第一个数字尽可能大；在第一个数字也达到最大值的前提下，使第二个数字尽可能大；依此类推，确定唯一的还原方案。

注意，在本题中，数字前允许出现前导 $0$。

输入格式

每行包含一个由不超过 $2000$ 个数字组成的字符串，表示一个测试用例。

一个输入文件中最多包含 $1000$ 个测试用例。

输出格式

对于输入文件中的每个测试用例，输出一行还原后的数字序列。

相邻两个数字之间用一个逗号分隔。

样例输入

189419111949
1000010

样例输出

1894,1911,1949
1,000010

数据范围

• 每个测试用例由不超过 $2000$ 个数字组成；
• 每个输入文件中最多包含 $1000$ 个测试用例。

来源与许可

本题为 HNOI 2003 试题「历史年份」，题面与测试数据整理自 BZOJ 1219。

样例 1

输入

189419111949
1000010

输出

1894,1911,1949
1,000010