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