Problem: A colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.

Input

The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

Output

Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

Examples

Input

6 3
ABBACC


Output

2
ABCACA


Input

3 2
BBB


Output

1
BAB

Solution (in PYTHON3):

Solution:
# Author : nitish420 --------------------------------------------------------------------
import os
import sys
from io import BytesIO, IOBase


def main():
	n,k=map(int,input().split())
	s=list(input())
	if n==1:
		print(0)
		print(s[0])
		exit()
	if k==2:
		a,b='A','B'
		# either it will be ababab or bababa so just check which one needs least number of modification .
		x,y=0,0
		# x : ababab, y:bababa
		for i,item in enumerate(s):
			if i%2:
				if item=='A':
					x+=1
				else:
					y+=1
			else:
				if item=='B':
					x+=1
				else:
					y+=1
		if x>y:
			print(y)
			print('BA'*(n//2)+'B'*(n%2))
		else:
			print(x)
			print('AB'*(n//2) + 'A'*(n%2))
	else:
		a,b,c='A','B','C'
		ans=0
		for i in range(1,n-1):
			if s[i]==s[i-1]:
				st=set([s[i-1],s[i+1]])
				if a not in st:
					s[i]=a
					ans+=1
				elif b not in st:
					s[i]=b
					ans+=1
				else:
					s[i]=c
					ans+=1
		if s[-1]==s[-2]:
			ans+=1
			if s[-2]==a:
				s[-1]=b
			else:
				s[-1]=a
		print(ans)
		print(*s,sep="")

'''
8 3
AABBABBB

'''


#----------------------------------------------------------------------------------------


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda: self.buffer.read().decode('ascii')
		self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


# endregion

if __name__ == '__main__':
	main()