题目描述

比尔试图通过折叠重复子序列来紧凑表示由大写字母 'A' 到 'Z' 组成的序列。例如，序列 AAAAAAAAAABABABCCD 的一种表示方法是 10 (A) 2 (BA) B2 (C) D。他形式化定义了折叠序列及其展开变换如下： 单个字符：由单个大写字母组成的序列是折叠序列，展开后为其自身。 连接操作：若 S 和 Q 是折叠序列，则 SQ 也是折叠序列。若 S 展开为 S'，Q 展开为 Q'，则 SQ 展开为 S'Q'。 重复操作：若 S 是折叠序列，X 是大于 1 的整数的十进制表示，则 X (S) 是折叠序列。若 S 展开为 S'，则 X (S) 展开为 S' 重复 X 次。 根据定义，展开折叠序列很容易，但比尔更关注逆变换：将给定序列折叠为字符数最少的折叠序列。若有多个解，输出任意一个即可。

输入

一行由 'A' 到 'Z' 组成的字符串，长度 1≤n≤100。

输出

输出最短的折叠序列，使其展开后等于输入字符串。若有多个解，输出任意一个。

输入示例 1

AAAAAAAAAABABABCCD

输出示例 1

9(A)3(AB)CCD

来源

2002 年东北欧竞赛

注：输出示例中的9(A)对应输入中连续 10 个 'A'（原题示例输出可能存在笔误，实际连续 10 个 'A' 的最短表示应为10(A)，但可能题目示例存在简化或特殊处理逻辑）。