Была строка \(s\), которую захотели зашифровать. Для этого взяли все \(26\) строчных латинских букв, расположили их в некотором порядке по кругу, после чего заменили каждую букву в \(s\) на ту, что является следующей по часовой стрелке, получив таким образом строку \(t\).
Вам дали строку \(t\). Определите лексикографически минимальную строку \(s\), из которой могла быть получена данная строка \(t\).
Строка \(a\) лексикографически меньше строки \(b\) такой же длины, если и только если:
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных выведите одну строку — лексикографически минимальную строку \(s\), из которой могла получиться \(t\).
Примечание
В первом наборе входных данных мы не могли иметь строку «a», поскольку тогда буква a переходила бы сама в себя, что невозможно. В качестве ответа нам подходит лексикографически вторая строка «b».
Во втором наборе нам не подходит «aa», поскольку a переходила бы в себя, и не подходит «ab», поскольку круг переходов замкнулся бы на \(2\) буквах, а он должен состоять из всех \(26\). Следующая строка «ac» нам подходит.
Ниже приведены схемы для первых трех наборов входных данных. В круге пропущены неучаствующие буквы, их можно расставить произвольно в пропуски.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy
|
b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz
|