Два рядки і називаються ізоморфними, якщо можна здійснити таке переобозначення всіх символів першого рядка, щоб отримати другий. При цьому різні символи повинні бути замінені на різні символи, а однакові — на однакові.
Наприклад, рядки "" і "" є ізоморфними. Відповідне переобозначення: символ '' замінюється на '', а символ '' на ''. Проте рядки "" і "" не є ізоморфними.
Вам дано рядок . Визначимо функцію ( — непорожній рядок), яка дорівнює кількості підрядків рядка , ізоморфних , помноженій на довжину рядка . Ваше завдання — знайти такий рядок , що складається з малих латинських букв, для якого значення є максимально можливим.
У першому рядку подано рядок (1 \leq |s| \leq 4000), який складається з малих латинських букв.
Виведіть оптимальний рядок . Якщо таких рядків декілька, виведіть будь-який з них. Виведений рядок повинен складатися з малих латинських букв.
Приклад 1