Ізоморфізми#5910

Ізоморфізми

2 секунди
512 мегабайтів
Складна

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading