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).


-----Examples-----
Input
3 3
cba

Output
NO

Input
3 4
cba

Output
cbd

Input
4 4
abcd

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_1 = t_1, ..., 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.

Difficulty: competition

Starter code:

Solutions:
3

import sys


def solve(s, k):
    l = len(s)
    for i in range(l-1, -1, -1):
        prev = s[max(i-2, 0):i]
        z = s[i] + 1
        while z in prev:
            z += 1
        if z >= k:
            continue
        # Gotcha!
        ret = s[:i] + [z]
        while len(ret) < l:
            prev = ret[max(len(ret)-2, 0):len(ret)]
            z = 0
            while z in prev:
                z += 1
            ret.append(z)
        return ret
    return None


def __starting_point():
    l, k = list(map(int, sys.stdin.readline().split()))
    s = [ord(c) - ord('a') for c in sys.stdin.readline().strip()]
    ans = solve(s, k)
    if ans is None:
        print('NO')
    else:
        print(''.join(chr(ord('a') + x) for x in ans))

__starting_point()

import sys

n, p = map(int, input().split())
s = input()
a = [(ord(s[i]) - ord('a') + 1) for i in range(n)]
curr = len(s) - 1
a += [p + 1, p + 1]
f = 0

def valid(x):
    nonlocal f
    if x == -1:
        return False
    if not (a[x] + 1 in (a[x - 1], a[x - 2])) and a[x] + 1 <= p:
        a[x] += 1
    elif not (a[x] + 2 in (a[x - 1], a[x - 2])) and a[x] + 2 <= p:
        a[x] += 2
    elif not (a[x] + 3 in (a[x - 1], a[x - 2])) and a[x] + 3 <= p:
        a[x] += 3
    else:
        return True
    print(s[:x], end = '')
    print(chr(a[x] + ord('a') - 1), end = '')
    tmp = 1
    ind = x
    while tmp in (a[x], a[x - 1]):
        tmp += 1
    for i in range(x + 1, len(s)):
        print(chr(tmp + ord('a') - 1), end = '')
        a[i] = tmp
        tmp = 1
        while tmp in (a[i], a[i - 1]):
            tmp += 1
    f = 1
    return False
            
while valid(curr):
    curr -= 1

if f == 1:
    return
    
print('NO')

n, p = map(int, input().split())

def f(t, k):
    a, b = min(t[k - 1], 2), min(t[k], 2)
    if a == b: a = 1
    return [3 - a - b, a, b]

def g(t, k):
    j = t[k]
    for i in range(j + 1, p):
        if i != t[k - 1] and i != t[k - 2]:
            t[k] = i
            return f(t, k)
    return None

def h(t):
    t = [ord(c) - 97 for c in t] + [27, 27]
    for k in range(n - 1, -1, -1):
        s = g(t, k)
        if s:
            d = n - k - 1
            t = t[: k + 1] + s * (d // 3) + s[: d % 3]
            return ''.join(chr(i + 97) for i in t)
    return 'NO'

t = input()
q = 'NO'
if p == 2:
    if t == 'a': q = 'b'
    elif t == 'ab': q = 'ba'
elif p > 2: q = h(t)
print(q)

n, p = map(int, input().split())
t, q = input(), 'NO'
if p == 2:
    if t == 'a': q = 'b'
    elif t == 'ab': q = 'ba'
elif p > 2: 
    t = [ord(c) - 97 for c in t] + [27, 27]
    for k in range(n - 1, -1, -1):
        for i in range(t[k] + 1, p):
            if i - t[k - 1] and i - t[k - 2]:
                t[k] = i
                a, b = min(t[k - 1], 2), min(t[k], 2)
                if a == b: a = 1
                t = t[: k + 1] + [3 - a - b, a, b] * (n // 3 + 1)
                print(''.join(chr(t[i] + 97) for i in range(n)))
                return
print(q)

n, p = map(int, input().split())
t = [ord(c) - 97 for c in input()] + [27, 27]
for k in range(n - 1, -1, -1):
    for i in range(t[k] + 1, p):
        if i - t[k - 1] and i - t[k - 2]:
            a, b = min(t[k - 1], 2), min(i, 2)
            if a == b: a = 1
            t = t[: k] + [i] + [3 - a - b, a, b] * (n // 3 + 1)
            print(''.join(chr(i + 97) for i in t)[: n])
            return
print('NO')

n, p = map(int, input().split())
s = list(ord(i) - 97 for i in input())

for i in range(n - 1, -1, -1):
    for j in range(s[i] + 1, p):
        if (i < 1 or j != s[i - 1]) and (i < 2 or j != s[i - 2]):
            s[i] = j
            for i in range(i + 1, n):
                for j in range(p):
                    if (i < 1 or j != s[i - 1]) and (i < 2 or j != s[i - 2]):
                        s[i] = j
                        break
            print(''.join(chr(i + 97) for i in s))
            return
print('NO')

def main():
    n, p = list(map(int, input().split()))
    l = [p, p] + [ord(c) - 97 for c in input()]
    a = l[-2]
    for i in range(n + 1, 1, -1):
        a, b = l[i - 2], a
        for x in range(l[i] + 1, p):
            if a != x != b:
                l[i] = x
                break
        else:
            continue
        break
    else:
        print("NO")
        return
    a, b = l[i - 1], x
    for i in range(i + 1, n + 2):
        for x in range(p):
            if a != x != b:
                l[i] = x
                a, b = b, x
                break
    print("".join(chr(x + 97) for x in l[2:]))


def __starting_point():
    main()

__starting_point()

n, p = map(int, input().split())
t = [ord(c) - 97 for c in input()] + [27, 27]
for k in range(n - 1, -1, -1):
    for i in range(t[k] + 1, p):
        if i - t[k - 1] and i - t[k - 2]:
            a, b = min(t[k - 1], 2), min(i, 2)
            if a == b: a = 1
            t = t[: k] + [i] + [3 - a - b, a, b] * (n // 3 + 1)
            print(''.join(chr(i + 97) for i in t)[: n])
            return
print('NO')

def trans(c):
  return chr(ord(c) + 1)

n, p = list(map(int, input().split()))
s = list(input())
s[n-1] = trans(s[n-1])

i = n - 1
while i >= 0 and i < n:
  if ord(s[i]) >= ord('a') + p:
    s[i] = 'a'
    i -= 1
    s[i] = trans(s[i])
  elif i > 0 and s[i] == s[i-1] or i > 1 and s[i] == s[i-2]:
    s[i] = trans(s[i])
  else:
    i += 1
else:
  print("NO" if i < 0 else "".join(s))


def trans(c):
  return chr(ord(c) + 1)

n, p = list(map(int, input().split()))
s = list(input())
s[n-1] = trans(s[n-1])

i = n - 1
while i >= 0 and i < n:
  if ord(s[i]) >= ord('a') + p:
    s[i] = 'a'
    i -= 1
    s[i] = trans(s[i])
  elif i > 0 and s[i] == s[i-1] or i > 1 and s[i] == s[i-2]:
    s[i] = trans(s[i])
  else:
    i += 1
else:
  print("NO" if i < 0 else "".join(s))

n, p = map(int, input().split())
t = [ord(c) - 97 for c in input()] + [27, 27]
for k in range(n - 1, -1, -1):
    for i in range(t[k] + 1, p):
        if i - t[k - 1] and i - t[k - 2]:
            a, b = min(t[k - 1], 2), min(i, 2)
            if a == b: a = 1
            t = t[: k] + [i] + [3 - a - b, a, b] * (n // 3 + 1)
            print(''.join(chr(i + 97) for i in t)[: n])
            return
print('NO')

def trans(c):

  return chr(ord(c) + 1)



n, p = list(map(int, input().split()))

s = list(input())

s[n-1] = trans(s[n-1])



i = n - 1

while i >= 0 and i < n:

  if ord(s[i]) >= ord('a') + p:

    s[i] = 'a'

    i -= 1

    s[i] = trans(s[i])

  elif i > 0 and s[i] == s[i-1] or i > 1 and s[i] == s[i-2]:

    s[i] = trans(s[i])

  else:

    i += 1

else:

  print("NO" if i < 0 else "".join(s))



# Made By Mostafa_Khaled


def trans(c):
  return chr(ord(c) + 1)

n, p = list(map(int, input().split()))
s = list(input())
s[n-1] = trans(s[n-1])

i = n - 1
while i >= 0 and i < n:
  if ord(s[i]) >= ord('a') + p:
    s[i] = 'a'
    i -= 1
    s[i] = trans(s[i])
  elif i > 0 and s[i] == s[i-1] or i > 1 and s[i] == s[i-2]:
    s[i] = trans(s[i])
  else:
    i += 1
else:
  print("NO" if i < 0 else "".join(s))

'''input
4 4
abcd
'''
# its just a simulation
from sys import stdin, setrecursionlimit
import heapq


# main starts
n, p = list(map(int, stdin.readline().split()))
string = list(stdin.readline().strip())
i = n - 1


def  check_pallindrome(string, index):
	if index > 1:
		if string[index - 1] != string[index] and string[index - 2] != string[index]:
			return True
		else:
			return False

	elif index > 0:
		if string[index - 1] != string[index]:
			return True
		else:
			return False

	else:
		return True


def get_next(string, index, p):
	if ord(string[index]) - 96  < p:
		string[index] = chr(ord(string[i]) + 1)
		if check_pallindrome(string, index):
			return True
		else:
			return get_next(string, index, p)
	else:
		return False

while True:
	# print(string)
	if i == n:
		print(''.join(string))
		break
	if i == -1:
		print("NO")
		break
	
	if get_next(string, i, p):
		i += 1
	else:
		string[i] = chr(96) 
		i -= 1

n, p = list(map(int, input().split()))
s = input()
slist = list(s)
bad = False
if p == 1:
    print('NO')
    bad = True
if p == 2:
    if s == 'a': print('b')
    elif s == 'ab': print('ba')
    else: print('NO')
    bad = True

def is_palindrome(a):
    if len(a) == 1:
        return False
    return a == list(reversed(a))

def _gen_banned(c, with_c=True):
    nonlocal slist
    banned = []
    if c-2 >= 0: banned.append(ord(slist[c-2]))
    if c-1 >= 0: banned.append(ord(slist[c-1]))
    if with_c: banned.append(ord(slist[c]))
    return banned
if not bad:
    for c in range(n-1, -1, -1):
        banned = _gen_banned(c)
        if sorted(banned) == [96+p-2, 96+p-1, 96+p]:
            continue
        else:
            #print('huh', c, banned)
            for i in range(ord(slist[c])+1, 96+p+1):
                if i not in banned:
                    slist[c] = chr(i)
                    break
            if slist[c] == s[c]:
                continue
            j = c+1
            while j < n:
                banned = _gen_banned(j, with_c=False)
                for i in range(97, 96+p+1):
                    if i not in banned:
                        slist[j] = chr(i)
                        break
                j += 1
            print(''.join(slist))
            break
    if ''.join(slist) == s:
        print('NO')



n, p = map(int, input().split())
p += ord('a') - 1
s = [*input()]

from string import ascii_lowercase
ap = [*ascii_lowercase]

def check(m):
	i = 1
	z = len(m)
	if z > 1 and m[0] == m[1]:
		return False
	while i < z - 1:
		t1 = m[i] + m[i + 1]
		t2 = m[i - 1] + m[i] + m[i + 1]
		if t1 == t1[::-1] or t2 == t2[::-1]:
			return False
		i += 1

	return True

i = n - 1
ans = 'NO'
t = s[i]

while i >= 0:
	if ord(t) == p:
		i -= 1
		t = s[i]
		continue

	t = chr(ord(t) + 1)
	m = [j for j in s]
	m[i] = t
	if check(m[:i + 1]):
		j = i + 1
		f = True
		while j < n:
			l = 97
			while l < 123:
				if (j >= 2 and ord(m[j - 2]) == l) or ord(m[j - 1]) == l:
					l += 1
				else:
					break
			if l == 123:
				f = False
				break
			m[j] = chr(l)
			j += 1
		m[i] = t
		if f:
			print(''.join(m))
			return

print(ans)

import sys

inf = float("inf")
# sys.setrecursionlimit(10000000)

# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# mod, MOD = 1000000007, 998244353
# words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'quarter',16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',25:'twenty five',26:'twenty six',27:'twenty seven',28:'twenty eight',29:'twenty nine',30:'half'}
# vow=['a','e','i','o','u']
# dx,dy=[0,1,0,-1],[1,0,-1,0]

# import random
# from collections import deque, Counter, OrderedDict,defaultdict
# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pi,gcd
# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right

def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()

def check_pallindrome(string,index):
    if index>1:
        if string[index]!=string[index-1] and string[index]!=string[index-2]:
            return True
        else:
            return False
    elif index>0:
        if string[index]!=string[index-1]:
            return True
        else:
            return False
    else:
        return True


def get_next(string,index,p):
    if ord(string[index])-96<p:
        string[index] = chr(ord(string[index])+1)
        if check_pallindrome(string,index):
            return True
        else:
            return get_next(string,index,p)
    else:
        return False

n,p = get_ints()
string = list(input())
i = n-1

while True:
    if i==n:
        print(''.join(string))
        break
    elif i==-1:
        print('NO')
        break
    if get_next(string,i,p):
        i+=1
    else:
        string[i] = chr(96)
        i-=1


def trans(c):
  return chr(ord(c) + 1)
n, p = list(map(int, input().split()))
s = list(input())
s[n-1] = trans(s[n-1]) #increment the last char 
i = n - 1
while i >= 0 and i < n:
  if ord(s[i]) >= ord('a') + p:
    s[i] = 'a'  #overflow make a 
    i -= 1
    s[i] = trans(s[i])# to make lexo larger ...inc the prev char #eg bc becomes ca for p=3 
  elif i > 0 and s[i] == s[i-1] or i > 1 and s[i] == s[i-2]:
    s[i] = trans(s[i]) # a pal substring is present..inc
  else:
    i += 1# good good..go on 
else:
  print("NO" if i < 0 else "".join(s))
  #if i became n ,,we are done 
  #else wwe have no ans 


#!/usr/bin/env python
# coding: utf-8

# In[11]:


n,p=map(int,input().split())
s=list(map(ord,input()))

i=n-1
s[i]+=1

p+=97

while ~i and i<n:
    
    if s[i]==p:
        s[i]=97
        i-=1
        s[i]+=1 
        
    elif i and s[i]==s[i-1]:
        s[i]+=1 
        
    elif i>1 and s[i]==s[i-2]:
        s[i]+=1 
        
        
    else:
        i+=1 
        
if i<0:
    print('NO')
    
else:
    #print('Yes')
    for i in s:
        print(chr(i),end='')
        
    
    



def solve(s, n):
    if len(s) == 1:
        return chr(ord(s[0]) + 1) if ord(s[0]) + 1 < ord('a') + n else 'NO'

    for i in reversed(range(2, len(s))):
        c = s[i]
        for j in range(ord(c)+1, ord('a')+n):
            next = chr(j)
            if next != s[i-1] and next!= s[i-2]:
                new_s = s[0:i] + next
                new_s = fill(new_s, n, s, i)
                return new_s
    for i in range(ord(s[1])+1, ord('a') + n):
        next = chr(i)
        if next != s[0]:
            new_s =  s[0] + next
            new_s = fill(new_s, n, s, 1)
            return new_s

    for i in range(ord(s[0]) + 1, ord('a') + n):
        next = chr(i)
        new_s = next
        new_s = fill(new_s, n, s, 0)
        return new_s
    return 'NO'

def fill(new_s, n, s, i):
    res = ['a', 'b', 'c']
    for x in range(i+1, len(s)):
        for y in res:
            if ord(y) < ord('a') + n and y != new_s[-1] and (len(new_s) < 2 or y != new_s[-2]):
                new_s += y
                break
    return new_s if len(new_s) == len(s) else 'NO'


m, n = list(map(int, input().split()))
s = input()
print(solve(s, n))

import sys
n, p = list(map(int, sys.stdin.readline().split()))
s = sys.stdin.readline()
sl = list(s)
sl.remove("\n")
flag = 0
for i in range(n-1, -1, -1):
    c = ord(s[i]) - 96
    prev = -1
    nprev = -1
    if c < p:
        if i-1 >= 0:
            prev = ord(s[i-1]) - 96
            if i-2 >= 0:
                nprev = ord(s[i-2]) - 96
        flag = 0
        for j in range(c+1, p + 1):
            if j != prev and j != nprev:
                sl[i] = chr(j+96)
                flag = 1
                break
        if flag:
            break
sn = "".join(sl).strip()
if s.strip() == sn:
    print("NO")
else:
    sn = sn[:i+1]
    while i < n-1:
        for j in range(26):
            if sn[-1] != chr(j+97):
                if i > 0 and sn[-2] != chr(j+97):
                    i += 1
                    sn += chr(j + 97)
                    break
                if i <= 0:
                    i += 1
                    sn += chr(j + 97)
                    break
    print(sn)


import sys
n, p = list(map(int, sys.stdin.readline().split()))
s = sys.stdin.readline()
sl = list(s)
sl.remove("\n")
flag = 0
for i in range(n-1, -1, -1):
    c = ord(s[i]) - 96
    prev = -1
    nprev = -1
    if c < p:
        if i-1 >= 0:
            prev = ord(s[i-1]) - 96
            if i-2 >= 0:
                nprev = ord(s[i-2]) - 96
        flag = 0
        for j in range(c+1, p + 1):
            if j != prev and j != nprev:
                sl[i] = chr(j+96)
                flag = 1
                break
        if flag:
            break
sn = "".join(sl).strip()
if s.strip() == sn:
    print("NO")
else:
    sn = sn[:i+1]
    while i < n-1:
        for j in range(26):
            if sn[-1] != chr(j+97):
                if i > 0 and sn[-2] != chr(j+97):
                    i += 1
                    sn += chr(j + 97)
                    break
                if i <= 0:
                    i += 1
                    sn += chr(j + 97)
                    break
    print(sn)


import sys
from math import log2,floor,ceil,sqrt,gcd
import bisect
# from collections import deque
# sys.setrecursionlimit(10**5)

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD =  1000000007

n,k = Ri()
st = ri()
st = [i for  i in st]
arr = [chr(ord('a')+i) for i in range(k)]
flag = -1
ch = -1
if n == 1:
    # YES()
    if st[0] == arr[-1]:
        NO()
    else:
        print(chr(ord(st[0])+1))
else:
    for i in range(n-1,-1,-1):
        for j in range(ord(st[i])-ord('a')+1, k):
            tch = arr[j]
            if i-2 >=0 :
                if tch == st[i-1] or tch == st[i-2]:
                    continue
                else:
                    flag = i
                    ch = tch
                    break
            elif i-1>= 0:
                if tch == st[i-1]:
                    continue
                else:
                    flag = i
                    ch = tch
                    break
            else:
                flag = i
                ch  = tch
                break
        if flag  != -1:
            break
    # print(flag)
    if flag == -1:
        NO()
    else:
        st[flag] = ch
        # print(st)
        # print(flag,n)
        for i in range(flag+1,n):
            # print("fs")
            for j in range(0, k):
                tch = arr[j]
                if i-2 >=0 :
                    if tch == st[i-1] or tch == st[i-2]:
                        continue
                    else:
                        flag = i
                        ch  = tch
                        st[i] = ch
                        break
                elif i-1>= 0:
                    if tch == st[i-1]:
                        continue
                    else:
                        flag = i
                        ch  = tch
                        st[i] = ch
                        break
                else:
                    flag = i
                    ch  = tch
                    st[i]    = ch
                    break
        # YES()
        print("".join(st))

n,p = list(map(int,input().split()))
s = ['#']+list(input())+['#']
s1=s[:]
aa='abcdefghijklmnopqrstuvwxyz'
ind=0
for i in range(n,0,-1):
    ind = aa.index(s[i])+1
    c=0
    ans=0
    while ind<p:
        if aa[ind]!=s[i-1] and aa[ind]!=s[i-2]:
            c=1
            ans=ind
            break
        ind+=1
    if c:
        s[i]=aa[ans]
        ind=i
        break
ans=0
p=3
for i in range(ind+1,n+1):
    ans=0
    while aa[ans%p]==s[i-2] or aa[ans%p]==s[i-1]:
        ans+=1
    s[i]=aa[ans%p]    
if s<=s1:
    print("NO")
    return
print(''.join(s[1:-1]))