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