# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Who Doesn't Love Shorter Strings?

By Reyad18 · Limits 1s, 512 MB

I hope you are not someone who hates longer strings, or fears longer strings like me. Strings can be a nightmare at any day of your competitive programming life. Hence, in this problem, we want to encode longer strings to shorter lengths. You will be given a string and the encoding rule is: x[encoded_string], where the encoded_string inside the square brackets is being repeated exactly x times. You can take any substring of the main string and replace it with it's encoded version. For example, you can take substring "aaaa" from "baaaa" and replace it with "4[a]", so the string will be " b4[a]". x should be a positive integer.

## Input

You will be given a string $s$ consisting lowercase English letters. The length of the string will be between $1$ to $300$.

## Output

Print the shortest string achievable by encoding. If there are several solutions, return the lexicographically smallest one.

## Samples

InputOutput
aaa

aaa


Can be encoded to 3[a], but it has more characters. So, original string is the shortest string achievable.

InputOutput
aabaabcaabaabc

2[2[aab]c]


### Statistics

0% Solution Ratio