Description

Xiao Ming has a modern history exam tomorrow. He decides to copy the historical events he needs to memorize onto a sheet of paper in ascending order by the year they occurred. However, when he copied them, adjacent years were too close to each other. For example, the three years $1894,1911,1949$ look like this on paper: 189419111949.

This troubles Xiao Ming, so he plans to write a program to restore these years to their correct form. How can we restore them correctly?

First, the years are strictly increasing in chronological order, so the restored sequence must also satisfy this requirement. But if that is the only constraint, then $1,89,419,111949$ would also satisfy it. Clearly, the last year cannot be that large, so Xiao Ming requires that, under this constraint, the last number be as small as possible.

With this additional restriction, $18,94,1911,1949$ also satisfies the condition. But since this is modern history, the first year would not be that early. Therefore, on the premise that the last number is minimized, Xiao Ming wants the first number to be as large as possible; and with the first number fixed at its maximum, the second number should be as large as possible; and so on.

Note: In this problem, leading zeros (i.e., leading $0$) are allowed.

Input Format

The input file contains multiple lines. Each line is a string consisting of no more than $2000$ digits, representing one test case. There are at most $1000$ test cases in a single input file.

Output Format

For each test case in the input file, output one corresponding line: the sequence of numbers after splitting, with adjacent numbers separated by a comma.

189419111949
1000010

1894,1911,1949
1,000010

Hint

Translated by ChatGPT 5