Билл пытается компактно представить последовательности прописных символов от \textbf{A} до \textbf{Z} с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность \textbf{AAAAAAAAAABABABCCD} - это \textbf{10(A)2(BA)B2(C)D}. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом: \begin{itemize} \item Последовательность, содержащая один символ от \textbf{A} до \textbf{Z}, является упакованной. Распаковка этой последовательности дает ту же последовательность из одного символа. \item Если \textbf{S} и \textbf{Q} - упакованная последовательность, то \textbf{SQ} - также упакованная последовательность. Если \textbf{S }распаковывается в \textbf{S′}, а \textbf{Q} распаковывается в \textbf{Q′}, то \textbf{SQ} распаковывается в \textbf{S′Q′}. \item Если \textbf{S} - упакованная последовательность, то \textbf{X}(\textbf{S}) - также упакованная последовательность, где \textbf{X}- десятичное представление целого числа, большего \textbf{1}. Если \textbf{S} распаковывается в \textbf{S′}, то \textbf{X}(\textbf{S}) распаковывается в \textbf{S′}, повторенную \textbf{X} раз. \end{itemize} Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов. \InputFile В первой строке находится последовательность символов от \textbf{A} до \textbf{Z}. Длина исходной последовательности от \textbf{1} до \textbf{100}. \OutputFile В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.