P1415 Split the Number Sequence

You are given a sequence of digits. You need to insert any number of commas to split it into a sequence of strictly increasing integers. If there are multiple solutions, output the one that minimizes the last number and, at the same time, is lexicographically largest (that is, first ensure the last number is minimized; if there are still multiple solutions, make the first number as large as possible; if there are still multiple solutions, make the second number as large as possible, and so on).

A single line containing the initial number.

A single line containing the sequence after splitting. Numbers are separated by commas, with no trailing comma.

Constraints Let the length of the input string be $l$. - For $10\%$ of the testdata, $l \le 5$. - For $30\%$ of the testdata, $l \le 15$. - For $50\%$ of the testdata, $l \le 50$. - For $100\%$ of the testdata, $l \le 500$. Source: adapted by lzn. Translated by ChatGPT 5