eolymp
bolt
Try our new interface for solving problems
Problems

Изоморфизмы – 2

Изоморфизмы – 2

Time limit 1 second
Memory limit 256 MiB

Две строки s и t называются изоморфными, если можно так переобозначить все буквы первой строки, чтобы получить вторую. Конечно, разные буквы должны быть переобозначены разными буквами, а одинаковые — одинаковыми.

Например, строки "aba" и "сас" изоморфные. Соответствующее переобозначение: обозначим букву 'a' буквой 'c', а букву 'b' буквой 'a'. А строки "xy" и "xx" не изоморфные.

Вам задана строка s. Введем функцию f(t) (t — непустая строка), которая равна количеству подстрок строки s, изоморфных t, умножить на длину строки t. Ваша задача, найти строку t, состоящую из маленьких латинских букв, такую, что значение f(t) максимально возможное.

Input data

В первой строке записана строка s (1|s|4000), строка состоит из маленьких латинских букв.

Output data

Выведите оптимальную строку t, если таких несколько, выведите любую. Выведенная строка должна состоять из маленьких латинских букв.

Examples

Input example #1
abacabadabacaba
Output example #1
abaca