Problem 3023 --递增序列

3023: 递增序列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 3
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

给定一个数字串,请你插入若干个逗号,使得该数字串成为一个严格递增的数列且最后一个数要尽可能小,在这个问题中,前导的零是允许出现在数的前面的。

Input

输入数据仅含一行,为一个长度不超过80的数字串。

Output

输出一个严格递增且最后一数最小的数列,相邻两个数之间用一个逗号隔开,如果有多个数列满足要求,则输出第一个数最大的那个数列,若这样的解还不止一个,则输出第二个数最大的那个数列,以此类推。

Sample Input

100000101

Sample Output

100,000101

HINT

Source

[Submit][Status]