Isomorphisms – 2

Two strings (s) and (t) are considered isomorphic if you can rename all the letters in the first string to transform it into the second one. Importantly, different letters must be renamed to different letters, and identical letters must remain identical.

For instance, the strings "(aba)" and "(cac)" are isomorphic. The renaming would be: change the letter '(a)' to '(c)', and '(b)' to '(a)'. However, the strings "(xy)" and "(xx)" are not isomorphic.

You are given a string (s). Define a 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 (f(t)) is maximized.

Input

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

Output

Output the optimal string (t); if there are multiple possibilities, you may output any one of them. The output string should consist of lowercase Latin letters.

Examples