Билл хочет сократить запись последовательности, состоящей из заглавных латинских букв. Для этого он может свернуть ее повторяющиеся подпоследовательности. Например, последовательность 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 символов.
В выходной файл выведите одну строку, содержащую наименьшую последовательность развертка которой даст строку, заданную во входном файле. Если ответов несколько - выведите любой из них.