Олимпиадный тренинг

Задача . A. Циклический сдвиг букв

Задача

Темы: жадные алгоритмы Конструктив реализация Строки *1200

Вам дана непустая строка s, состоящая из строчных букв английского алфавита. Требуется ровно один раз выбрать в s непустую подстроку и сдвинуть её буквы по циклу: «z» $\text{[math]}$ «y» $\text{[math]}$ «x» $\text{[math]}$ «b» $\text{[math]}$ «a» $\text{[math]}$ «z», то есть заменить каждую букву подстроки на предыдущую в английском алфавите (а букву «a» на букву «z»).

Требуется определить, какую лексикографически минимальную строку можно получить после выполнения ровно одного сдвига?

Входные данные

В первой строке входных данных записана строка s (1 ≤ |s| ≤ 100 000), состоящая из строчных букв английского алфавита.

Выходные данные

Выведите лексикографически минимальную строку, которую можно получить из s, сдвинув ровно одну непустую подстроку.

Примечание

Строка s называется лексикографически меньшей, чем строка t такой же длины, если существует такое 1 ≤ i ≤ |s|, что s₁ = t₁, s₂ = t₂, ..., s_i - 1 = t_i - 1, а s_i < t_i.

Примеры

№	Входные данные	Выходные данные
1	codeforces	bncdenqbdr
2	abacaba	aaacaba

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет