Петя записал на листке бумаги последовательность цифр. Теперь он хочет добавить между некоторыми цифрами запятые, чтобы если объединить цифры, не разделенные запятыми, в числа, получилась бы возрастающая последовательность. Среди таких последовательностей Петя хочет получить такую, в которой максимальное число минимально. Среди таких последовательностей Петя хочет выбрать ту, в которой первое число максимально, при прочих равных - в которой максимально второе, и т. д. В числах разрешаются ведущие нули. \InputFile Входной файл содержит последовательность цифр. Длина последовательности не превышает \textbf{1000}. \OutputFile Выведите в выходной файл последовательность с добавленными в нужных местах запятыми.