Comma Partitioning for Strictly Increasing Sequence

Given a string of digits, insert commas to split it into several strictly increasing numbers. You must insert at least one comma so that the string is split into at least two parts. Among all valid partitions, you should choose the one where the last number is minimized. If there are multiple partitions with the same last number, choose the one which is lexicographically largest, i.e. the first number should be as large as possible; if they tie then the second number should be as large as possible; and so on.

Formally, let the split sequence be \(a_1, a_2, \ldots, a_k\) (with \(k \ge 2\)) where each \(a_i\) is an integer and \(a_1 < a_2 < \cdots < a_k\). Among all valid sequences, pick one that minimizes \(a_k\); if there is a tie, then maximize \(a_1, a_2, \ldots, a_{k-1}\) in lexicographical order.

Note: Numbers cannot have leading zeros unless the number is exactly \(0\).

inputFormat

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

outputFormat

Output the chosen valid partition by printing the numbers separated by commas. If no valid partition exists, output an empty line.

sample

1234

1,23,4