Паша ненавидит палиндромы. Он считает строку s терпимой, если каждый ее символ — это одна из первых p букв латинского алфавита, и s не содержит ни одной подстроки-палиндрома длины 2 или больше.
Паша нашел терпимую строку s длины n. Помогите ему найти лексикографически следующую терпимую строку той же длины, либо определите, что такой не существует.
Выходные данные
Если лексикографически следующая терпимая строка той же длины существует, выведите ее. В противном случае выведите «NO» (без кавычек).
Примечание
Строка s лексикографически больше (или просто больше) строки t той же длины, если существует число i, такое что s1 = t1, ..., si = ti, si + 1 > ti + 1.
Лексикографически следующая терпимая строка — это лексикографически минимальная терпимая строка, большая данной.
Палиндром — это строка, которая одинаково читается слева направо и справа налево.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
cba
|
NO
|
|
2
|
3 4
cba
|
cbd
|
|
3
|
4 4
abcd
|
abda
|