说明

本题差SPJ，欢迎大家提供标准SPJ

题目描述

比尔正在试图用折叠重复子序列的方式紧凑的表示由大写字母 A 到 Z 组成的字符序列。

例如，表示序列 AAAAAAAAAABABABCCD 的一种方式是 10(A)2(BA)B2(C)D。

他通过以下方式定义了折叠的字符序列以及它们的展开变换：

• 包含单个字符的序列被认为是折叠序列，展开它得到的序列为它本身。
• 如果$S$和 $Q$是两个折叠序列，并且 $S$可以展开得到 $S$′，$Q$可以展开得到 $Q$′，则认为$SQ$也是一个折叠序列，并且 $SQ$展开得到$S$′$Q$′。
• 如果 $S$ 是折叠序列，则 $X(S)$也是折叠序列，其中 $X$为大于 1 的整数。如果 $S$展开得到 $S$′，则 $X(S)$展开得到 $X$ 个 $S$′。

根据定义可以展开任意给出的折叠序列，现在给出原序列，请你将它折叠，并使得折叠序列包含尽可能少的字符数。

输入格式

输入包含一行由大写字母构成的字符序列，序列长度在 1 到 100 之间。

输出格式

输出包含字符数最少的折叠序列，如果答案不唯一则任意输出一个即可。

样例

AAAAAAAAAABABABCCD

9(A)3(AB)CCD

来源

• POJ2176
• 算法竞赛进阶指南