Martian DNA Formula

Person A has discovered the DNA formula of Martians.

A wants to give this information to B in exchange for a large amount of peanuts. Since they suspect that an organization trying to stop the formula from spreading may be listening, they decide to meet in a deserted bakery and exchange the goods there.

The formula is very long, so A wants to write it as briefly as possible before handing it over. The shortening rule is as follows.

The formula is a string consisting only of lowercase English letters. If a string is repeated several times, the repeated part may be written inside parentheses followed by the number of repetitions. For example, abcabcabc can be written as (abc)3, and axyxyxyxyb can be written as a(xy)4b. Shortenings may also be nested, so mnmndefmnmndef can be written as ((mn)2def)2.

The length of a written formula is the total number of characters, including parentheses and digits.

Given a formula, output a shortened form whose written length is as small as possible.

The optimal form does not have to be unique.

The input consists of one line containing the DNA formula. The formula has length at most 1000.

Output one line containing the shortest way to write the formula. If there is more than one expression with minimum length, output any one of them.