描述

给定一个由数字组成的字符串，插入逗号以创建一个严格递增的数字序列，从而最小化最后一个数字的大小。对于这个问题，允许在数字前面有前导零。

输入

输入将包含多个测试用例。每个测试用例由一行组成，包含一个最多长度为 $80$ 的数字字符串。一行仅包含数字 $0$ 时，表示输入结束。

输出

对于每个测试用例，输出由逗号分隔的严格递增的数字序列，且逗号和数字之间没有空格。如果有多个这样的序列，选择其中第一个数字最大的一种；如果存在平局，则选择第二个数字最大的一种，以此类推。

3456
3546
3526
0001
100000101
0

3,4,5,6
35,46
3,5,26
0001
100,000101

来源

East Central North America 2002