#1492. [HNOI2003]历史年份History

[HNOI2003]历史年份History

题目描述

明天就要考近代史了,小明决定把要背的历史事件,根据事件发生的年份,按顺序从小到大抄在一张纸上。 可是他抄的时候,相邻两个年份相隔太近了。例如 189419111949 这三个时间,由于相隔太近 纸上写的是: 189419111949

这使小明很苦恼,于是他准备编写个程序把这些年份还原成应该的样子。那么,怎么才能够正确的还原呢? 首先,这些年份是按时间顺序严格递增排列的,所以,还原后的也必须满足这点要求。

但如果仅仅是这样,那么 189419111949 也满足要求。显然,最后的年份不可能有这么大,所以,小明要求在这个条件下 最后一个数要最小。

加了这个限制后, 189419111949 也满足条件,但因为是近代史,第一个年份不会这么早,所以小明 还要在保证最后一个数最小的前提下,第一个数要尽量大。并在保证第一个数最大的情况下,第二个数最大……以此类推。

注意:在本题中,数字前的前导 0 是被允许的。

输入格式

每一行是一个由不超过 20002000 个数字组成的字符串 ss ,表示一个测试例子。

输出格式

相对于输入文件的每一个测试例子,你的程序要输出对应的一行,即是分隔后的数字序列相邻的两个数用一个逗号分隔。

样例输入

189419111949
1000010

样例输出

1894,1911,1949
1,000010

数据范围与约定

对于 100%100\% 的数据,1s20001\le |s|\le 2000,一个输入文件中最多包含 10001000 个测试例子。