Саша недавно начала регистровать компанию по разработке чат-ботов и уже подала необходимые документы. Но добрые люди рассказали Саше, что в телефонном справочнике компании располагаются в лексикографически возрастающем порядке их названий. Что такое телефонный справочник, Саша не знает, но решила учесть рекомендации и поменять название своей компании, чтобы оно было как можно раньше в телефонном справочнике. Поскольку Саша уже подала документы, она не может полностью поменять название компании, но может сказать, что допустила опечатку, и поменять любые две буквы в названии местами. Помогите Саше выбрать новое название компании или оставить текущее.
В единственной строке содержится одно слово, состоящее из строчных латинских букв (от «a» до «z») длиной $$$n$$$ ($$$2 \leq n \leq 10^6$$$).
Выведите одно слово — новое название компании. Если название не изменилось, выведите изначальное название.
Решения, верно работающие при $$$n \leq 10$$$, будут оцениваться в $$$20$$$ баллов.
Решения, верно работающие при $$$n \leq 100$$$, будут оцениваться в $$$40$$$ баллов.
Решения, верно работающие при $$$n \leq 3\,000$$$, будут оцениваться в $$$60$$$ баллов.
Решения, верно работающие при $$$n \leq 50\,000$$$, будут оцениваться в $$$80$$$ баллов.
aefbz
abfez
abc
abc
