#3442. 折叠序列 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

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

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

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

1、包含带个字符的序列被认为是折叠序列,展开它得到的序列为它本身。

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

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

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

输入格式

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

输出格式

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

样例

样例输入

AAAAAAAAAABABABCCD

样例输出

9(A)3(AB)CCD

数据范围与提示

POj 2176