题目描述

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

例如，表示序列$\red {AAAAAAAAAABABABCCD}$的一种方式是$\red {10（A）2（BA）B2（C）D}$。

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

$\red {1}$、包含带个字符的序列被认为是折叠序列，展开它得到的序列为它本身。

$\red {2}$、如果$\red {S}$和$\red {Q}$是两个折叠序列，并且$\red {S}$可以展开得到$\red {S’}$，$\red {Q}$可以展开得到$\red {Q’}$，则认为$\red {SQ}$也是一个折叠序列，并且$\red {SQ}$展开得到$\red {S’Q’}$。

$\red {3}$、如果$\red {S}$是折叠序列，则$\red {X(S)}$也是折叠序列，其中$\red {X}$为大于$\red {1}$的整数。如果$\red { S}$展开得到$\red {S’}$，则$\red {X(S)}$展开得到$\red {X}$个$\red {S’}$。

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

输入格式

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

输出格式

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

样例

输入样例

AAAAAAAAAABABABCCD

输出样例

9(A)3(AB)CCD