Just add commas

Petya has written a sequence of digits on a piece of paper. He now wants to insert commas between some of these digits to form a sequence of numbers that is strictly increasing.

Among all possible sequences, Petya aims to create one where the largest number is as small as possible. If there are multiple sequences with the same largest number, he prefers the one where the first number is as large as possible. If there's still a tie, he wants the second number to be as large as possible, and so on. Note that numbers can have leading zeros.

Input

The input consists of a single line containing a sequence of digits. The sequence's length does not exceed 1000.

Output

Output the sequence with commas inserted at the appropriate positions.

Examples