Білл намагається компактно подати послідовности прописних символів від A до Z при допомозі пакування повторюваних підпослідовностей всередині них. Наприклад, один зі способфв подати послідовність AAAAAAAAAABABABCCD - це 10(A)2(BA)B2(C)D. Він формально визначає стиснуті послідовності символів і правила переведення їх у неупакований вид наступним чином:
Послідовність, що містить один символ вівд A до Z, є упакованою. Розпаковка цієї послідовності дає цю ж послідовність з одного символу.
Якщо S і Q - упаковані послідовності, то SQ - також упакована послідовність. Якщо S розпаковується в S′, а Q роспаковується в Q′, то SQ роспаковується в S′Q′.
Якщо S - упакована послідовність, то X(S) - також упакована послідоність, де X- десяткове подання цілого числа, більшого 1. Якщо S розпаковується в S′, то X(S) розпаковується в S′, повторену X разів.
Дотримуючись цих правил, легко розспаковати довільну задану упаковану послідовність. Проте Біллу більш цікавий зворотній перехід. Він хоче упакувати послідовність так, щоб результуюча стиснена послідовність містила найменше можливе число символів.
У першому рядку знаходиться послідовність символів від A до Z. Довжина заданої послідовності від 1 до 100.
У єдиному рядку виводиться упакована послідовність найменшої довжини, яка розпаковується у задану послідовність. Якщо таких послідовностей декілька, можна вивести довільну.