Description

One day, the intelligence agency obtained a secret file. Its content is an encrypted string consisting entirely of uppercase letters. The director, Xiaoming, wants to send it to his old friend Xiaoliu on the mysterious "xx" continent in the Far East for decryption. However, if the string is too long, transmission takes too much time and is unsafe, so Xiaoming wants to shorten it as much as possible.

He sets the following shortening rule: If a string t appears consecutively k times, it can be represented as k(t). For example, ABABAB can be shortened to 3(AB). Repeated (nested) shortening is allowed. For example, ABABABAAAAAAABABABAAAAAA can be shortened to 2(3(AB)6(A)).

Now, given the string, determine the shortest possible result after applying the shortening rule.

Note: If there are multiple optimal answers, output the lexicographically largest one (thanks to @Dilute.).

Input Format

A single line containing the given string. The string consists only of uppercase letters.

Output Format

A single line containing the string after shortening.

AAAAAAAAAABABABCCD

9(A)3(AB)CCD

Hint

Constraints.

• For 100% of the testdata, the string length $L \le 100$.
• The testdata has certain gradation.

Translated by ChatGPT 5