Who Doesn't Love Shorter Strings?

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

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

Input	Output
aabaabcaabaabc	2[2[aab]c]