← 返回题目列表

Codeforces · 464/A

A. 拒绝回文!

中文机器翻译题面 查看原题

Paul 讨厌回文。他假设如果字符串 s 的每个字符都是英文字母表的前 p 个字母之一,并且 s 不包含任何长度为 2 或以上的回文连续子串,则字符串 s 是可以容忍的。

Paul 找到了长度为 n 的可容忍字符串 s。帮助他找到按字典顺序排列的下一个相同长度的可容忍字符串,否则说明该字符串不存在。

输入

第一行包含两个以空格分隔的整数:n 和 p (1 ≤ n ≤ 1000;1 ≤ p ≤ 26)。第二行包含字符串s,由n个小英文字母组成。保证字符串是可以容忍的(根据上面的定义)。

输出

如果按字典顺序存在相同长度的下一个可容忍字符串,则打印它。否则,打印“NO”(不带引号)。

示例

输入 #1

3 3
cba

输出 #1

NO

输入 #2

3 4
cba

输出 #2

cbd

输入 #3

4 4
abcd

输出 #3

abda

注意

如果有数字 i,则字符串 s 按字典顺序大于(或简单地大于)相同长度的字符串 t,使得 s1 = t1, ..., si = ti, si + 1 > ti + 1。

按字典顺序排列的下一个可容忍字符串是按字典顺序排列的最小可容忍字符串,它大于给定的字符串。

回文是正向或反向读取相同的字符串。