Problem E: 数组分拆Ⅱ

Problem E: 数组分拆Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 47  Solved: 18
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI得到了一串数字作为他的新年礼物,他非常喜欢这串数字!

在仔细研究了几天之后,PIPI成功的将这串数字拆成了若干段,并且从左往右每段形成的新数字严格递增。

这样的拆分方式有很多种,现在PIPI想知道最后一个数字最小的同时,字典序最大的拆分方式。

即首先要满足拆分后最后一个数字尽可能的小,如果有多组解,则使得第一个数尽量大;如果仍有多组解,则使得第二个数尽量大,依次类推……

Input

第一行给出一个数字串,长度不超过500.

Output

从左往右的顺序输出拆分后的数字,相邻数字用空格隔开。注意对于每个数字,如果其有前导0,也要输出。

Sample Input

3456

Sample Output

3 4 5 6

HINT

注意前导0的情况。