Свертка
Билл хочет сократить запись последовательности, состоящей из заглавных латинских букв. Для этого он может свернуть ее повторяющиеся подпоследовательности. Например, последовательность AAAAAAAAAABABABCCD может быть записана как 10(A)2(BA)B2(C)D. Формальное определение свернутой последовательности и соответствующей ей операции развертки дается следующим образом:
Последовательность, которая содержит единственный символ от 'A' до 'Z' представляет из себя свернутую последовательность. При развертке такой последовательности получается она сама.
Если S и Q - свернутые последовательности, то SQ также свернутая последовательность. Если при развертке строки S получается строка S', а при развертке Q получается Q', то при развертке SQ получается строка S'Q'.
Если S - свернутая последовательность, то X(S) также свернутая последовательность, где X это десятичное представление целого числа большего единицы. Если при развертке строки S получается строка S', то при развертке X(S) получается строка S', повторенная X раз.
Билл хочет свернуть заданную последовательность таким образом, чтобы результат содержал наименьшее число символов.
Входные данные
Входной файл содержит непустую строку, состоящую из заглавных латинских букв. Длина строки не превышает 100 символов.
Выходные данные
В выходной файл выведите одну строку, содержащую наименьшую последовательность развертка которой даст строку, заданную во входном файле. Если ответов несколько - выведите любой из них.