Description

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).

Input Format

A single line containing the initial number.

Output Format

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

3456

3,4,5,6

3526

3,5,26

3546

35,46

0001

0001

100000101

100,000101

Hint

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