Description

你有许多由小写字母组成的字符串需要通过电子邮件发送，但其中一些太长，按原样输入会很费力。由于你发现其中有重复的部分，你决定尝试一种简单的压缩方法：将重复的序列用括号括起来，并在前面加上表示重复次数的数字。例如，字符串 “abababaaaaa” 可以表示为 “3(ab)5(a)” 或 “a3(ba)4(a)”。压缩表示的语法如下，以巴科斯-瑙尔范式给出，起始符号为 $S$。

$$\begin{aligned} &\langle S \rangle ::= \langle R \rangle \mid \langle R \rangle \langle S \rangle \\ &\langle R \rangle ::= \langle L \rangle \mid \langle D \rangle \ (\langle S \rangle) \\ &\langle D \rangle ::= 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \\ &\langle L \rangle ::= \text{a} \mid \text{b} \mid \text{c} \mid \text{d} \mid \text{e} \mid \text{f} \mid \text{g} \mid \text{h} \mid \text{i} \mid \text{j} \mid \text{k} \mid \text{l} \mid \text{m} \mid \text{n} \mid \text{o} \mid \text{p} \mid \text{q} \mid \text{r} \mid \text{s} \mid \text{t} \mid \text{u} \mid \text{v} \mid \text{w} \mid \text{x} \mid \text{y} \mid \text{z} \end{aligned}$$

注意，重复次数由单个数字指定，因此最多为九次，但可以通过嵌套指定更多重复。例如，三十个 a 的字符串可以表示为 “6(5(a))” 或 “3(5(2(a)))”。

请找出给定字符串在这种压缩方案下最短的可能表示。

Input Format

输入是一行包含一个小写字母字符串。字符串中的字母数量至少为 $1$，最多为 $200$。

Output Format

输出一行，包含输入字符串最短的可能表示。如果存在两个或更多个最短表示，输出其中任意一个均可接受。

abababaaaaa

3(ab)5(a)

abababcaaaaaabababcaaaaa

2(3(ab)c5(a))

abcdefg 

abcdefg

Hint

翻译由 DeepSeek V3 完成