Сегодня на уроке класс Васи проходил различные алгоритмы кодирования данных. Однако, уже придуманные алгоритмы кодирования его не заинтересовали, и он решил придумать свой собственный. Первый метод, который пришел ему в голову, выглядел так: каждый символ строки, состоящей из латинских строчных символов, кодируется числом от 1 до 26 в обратном алфавитном порядке (символ 'a' кодируется числом 26, символ 'b' — числом 25, и т.д.), а затем все эти числа записываются в одну строку подряд без пробелов. Например, строка abza будет закодирована следующим образом: 2625126.
Все бы ничего, но Васин метод оказался не очень эффективен — полученное закодированное сообщение не всегда можно единственным образом декодировать. Однако, Вася решил, что это не такая большая проблема — вместо этого он решил по полученному коду восстанавливать строку минимальной возможной длины. Если таких строк несколько, ему все равно, какую из них он найдет. Помогите ему с этой задачей.
Формат входного файла
В первой строке входного файла input.txt записана строка, состоящая из цифр. Ее длина не превосходит 100.
Гарантируется, что строка получена в результате применения Васиного алгоритма кодирования к некоторой строке, состоящей только из строчных латинских букв.
Формат выходного файла
В выходной файл output.txt требуется вывести раскодированную строку — строку, после применения к которой алгоритма Васи, получается строка, данная во входном файле. Из всех возможных вариантов таких строк, строка в ответе должна иметь минимальную возможную длину. Если строк минимальной длины несколько, разрешается вывести любую их них.
Пример входных и выходных данных
input.txt_____output.txt_______Комментарий
219_________yh____________ Символ 'y' кодируется в число 2, а символ 'h' в число 19. Также правильным ответом является строка "fr".
271________ ytz_____________Других вариантов декодирования нет.