Ізоморфізми – 2#5938

Ізоморфізми – 2

1 секунда
256 мегабайтів
Дуже складна

Два рядки і називаються ізоморфними, якщо можна здійснити таке переобозначення всіх символів першого рядка, щоб отримати другий. При цьому різні символи повинні бути замінені на різні символи, а однакові — на однакові.

Наприклад, рядки "" і "" є ізоморфними. Відповідне переобозначення: символ '' замінюється на '', а символ '' на ''. Проте рядки "" і "" не є ізоморфними.

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

Вхідні дані

У першому рядку подано рядок (1 \leq |s| \leq 4000), який складається з малих латинських букв.

Вихідні дані

Виведіть оптимальний рядок . Якщо таких рядків декілька, виведіть будь-який з них. Виведений рядок повинен складатися з малих латинських букв.

Приклади

Приклад 1

Loading
Loading