Просто добавь запятые

Петя записал на листке бумаги последовательность цифр. Теперь он хочет добавить между некоторыми цифрами запятые, чтобы если объединить цифры, не разделенные запятыми, в числа, получилась бы возрастающая последовательность.

Среди таких последовательностей Петя хочет получить такую, в которой максимальное число минимально. Среди таких последовательностей Петя хочет выбрать ту, в которой первое число максимально, при прочих равных - в которой максимально второе, и т. д. В числах разрешаются ведущие нули.

Входные данные

Входной файл содержит последовательность цифр. Длина последовательности не превышает 1000.

Выходные данные

Выведите в выходной файл последовательность с добавленными в нужных местах запятыми.

Примеры