Folding#5179
Bill is trying to compactly represent sequences consisting of capital Latin letters from A to Z by folding repeating subsequences within them. For example, one way to represent the sequence AAAAAAAAAABABABCCD is 10(A)2(BA)B2(C)D. He formally defines folded sequences of characters, along with the corresponding unfolding transformation, as follows:
A sequence that contains a single character from A to Z is considered a folded sequence. Unfolding such a sequence produces the same single character.
If S and Q are folded sequences, then SQ is also a folded sequence. Unfolding S to S' and Q to Q' means that unfolding SQ results in S'Q'.
If S is a folded sequence, then X(S) is also a folded sequence, where X is a decimal representation of an integer greater than . If S unfolds to S', then X(S) unfolds to S' repeated X times.
According to this definition, it is easy to unfold any given folded sequence. However, Bill is more interested in the reverse transformation. He wants to fold the given sequence such that the resulting folded sequence contains the least possible number of characters.
The input consists of a single line containing between and capital Latin letters (A–Z).
Output a single line containing the shortest possible folded sequence that unfolds to the given input sequence. If there are several answers, output any one of them.
Example 1