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:
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="")