Restore Historical Years

In modern history exams, Xiao Ming needs to memorize a list of historical events, each marked by the year they occurred. He wrote down all the years in a single line without any separators. For example, instead of writing "1894,1911,1949" the paper shows "189419111949" because the adjacent years are too close.

The task is to restore the original list of years from the concatenated string. The years in the restored list must satisfy two conditions:

1. The years must be in strictly increasing order.
2. Among all valid segmentations the one with the smallest last year is chosen. In case of a tie (i.e. several segmentations have the same last year), the segmentation with the largest first year is chosen. If there is still a tie, then the second year should be as large as possible, and so on.

Note: Leading zeros are allowed in a year.

Example:

For the input string "189419111949", two possible segmentations are:

• 18,94,1911,1949 (last = 1949, first = 18)
• 1894,1911,1949 (last = 1949, first = 1894)

Both segmentations are valid (the years are in strictly increasing order and the final year is 1949). However, since 1894 > 18, the second segmentation is chosen.

Your program should output the correct segmentation by inserting commas between the restored years.

Hint (for the algorithm design): Use dynamic programming with recursion and memoization. When comparing two valid segmentations, if we denote the segmentation as a sequence a₁, a₂, …, a_k, then the optimization criteria are:

• Minimize \(a_k\) (the last number): \(a_k\) should be as small as possible.
• Among all segmentations having the same \(a_k\), choose the one with the maximum \(a_1\); if there is still a tie, choose the one with the maximum \(a_2\); and so on.

Formally, if we compare two segmentation sequences \(P = [p_1, p_2, \dots, p_k]\) and \(Q = [q_1, q_2, \dots, q_m]\), then
\( P \text{ is better than } Q \iff \begin{cases} p_k q_i. \end{cases} \)

inputFormat

The input consists of a single line containing a non-empty string of digits.

outputFormat

Output the restored sequence of years by inserting commas between the segments. There should be no extra spaces.

sample

189419111949

1894,1911,1949