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