Petya has written a sequence of digits on a piece of paper. He now wants to insert commas between some of these digits so that the segments of digits separated by commas form a strictly increasing sequence of numbers.
Among all such sequences, Petya wants to achieve one where the largest number is as small as possible. If there are multiple possibilities with the same largest number, he chooses the one where the first number is as large as possible; if there's still a tie, he prefers the one with the second number as large as possible, and so on. Numbers may have leading zeros.
The input contains a sequence of digits. The length of the sequence does not exceed .
Output the sequence with commas inserted at the appropriate positions.
Example 1