Secret Message Compression

An intelligence agency has intercepted a secret document containing a long sequence of uppercase letters that has been encrypted. The agency chief, Xiao Ming, wants to send the encrypted message to his friend Xiao Liu on the mysterious continent of XX in the east for decryption. However, the longer the string the longer it takes to send and the less secure it becomes. To solve this problem, Xiao Ming devised a compression scheme:

If a substring t appears consecutively k times in the string, it can be represented as \(k(t)\). For example, ABABAB can be compressed to 3(AB). Repeated (nested) compression is allowed; for instance, ABABABAAAAAAABABABAAAAAA can be compressed to 2(3(AB)6(A)).

Your task is: given an input string consisting of uppercase letters only, find its shortest compressed form using the above rule. If there are multiple optimal compressions (of the same minimal length), output the one that is lexicographically largest.

Note: Lexicographical comparison is based on the standard dictionary order.

inputFormat

The input consists of a single line containing a string of uppercase letters.

outputFormat

Output the compressed string which is the shortest possible according to the compression rules. If there are several optimal solutions, output the lexicographically largest one.

sample

ABABAB

3(AB)