Isomorphisms

Two strings (s) and (t) are considered isomorphic if you can remap all the characters of the first string to form the second string. This remapping must ensure that different characters map to different characters, and identical characters map to identical ones.

For instance, the strings "(aba)" and "(cac)" are isomorphic. The remapping here is: map the character '(a)' to '(c)', and '(b)' to '(a)'. Conversely, the strings "(xy)" and "(xx)" are not isomorphic.

You are given a string (s). Define the function (f(t)) (where (t) is a non-empty string) as the number of substrings of (s) that are isomorphic to (t), multiplied by the length of (t). Your task is to find a string (t), composed of lowercase Latin letters, such that the value of (f(t)) is maximized.

Input

The first line contains the string (s) ((1 $\le$ |s| $\le$ 2000)), which consists of lowercase Latin letters.

Output

Output the optimal string (t). If there are multiple such strings, output any one. The output string should consist of lowercase Latin letters.

Examples