No to Palindromes!

1000ms

262144K

Description:

Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and s doesn't contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.

Input:

The first line contains two space-separated integers: n and p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). The second line contains string s, consisting of n small English letters. It is guaranteed that the string is tolerable (according to the above definition).

Output:

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print "NO" (without the quotes).

Sample Input:

3 3
cba

Sample Output:

NO

Sample Input:

3 4
cba

Sample Output:

cbd

Sample Input:

4 4
abcd

Sample Output:

abda

Note:

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s₁ = t₁, ..., s_i = t_i, s_i + 1 > t_i + 1.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

Informação

Provedor Codeforces

Código CF464A