Билл пытается компактно представить последовательности прописных символов от 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 раз.
Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов.
Ограничения: длина исходной последовательности от 1 до 100.
Входные данные
В первой строке находится последовательность символов от A до Z.
Выходные данные
В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
AAAAAAAAAABABABCCD
|
9(A)3(AB)CCD
|
|
2
|
NEERCYESYESYESNEERCYESYESYES
|
2(NEERC3(YES))
|