题目描述

某天，情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的 xx 大陆上的老朋友小刘来解密。然而若字符串太长，则需要很长的发送时间，太不安全了，因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则：若一个字符串 $t$ 连续出现 $k$ 次，则可以用 $k(t)$ 进行说明。如 ABABAB 可以缩成 3(AB)。当然，重复缩短是允许的，如 ABABABAAAAAAABABABAAAAAA 可以缩成 2(3(AB)6(A))。

现在，小明想知道，对于给定的字符串，最短可以缩成什么样子。

注意：有多个最优方案时，输出其中字典序最大的。( thanks to @Dilute. )

输入格式

输入仅一行，为给定的字符串。

输出格式

输出仅一行，为经过缩短操作后的字符串。

AAAAAAAAAABABABCCD

9(A)3(AB)CCD

提示

【数据范围】

对于 $100\%$ 的数据，字符串的长度 $L \le 100$。数据存在一定梯度。