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 PYTHON):

Solution:
import sys
import heapq
import bisect

INF = 10**9+7
OFFLINE = 0
sys.setrecursionlimit(INF)

##
if OFFLINE:
	sys.stdin = open("fin.txt", "r")
	sys.stdout = open("fout.txt", "w")
##

def wt(s, test):
	w = 0
	for i in range(len(s)):
		if s[i] != test[i]:
			w += 1
	return w


#main

MAP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

n, k = map(int, sys.stdin.readline().split())
s = raw_input()
s = list(s)


W = 0
if k == 2:
	test = []
	test2 = []
	for i in range(n):
		test.append(MAP[i%2])
		test2.append(MAP[(i+1)%2])

	w1 = wt(s, test)
	w2 = wt(s, test2)

	if w1 < w2:
		sol = ''.join(test)
		print w1
		print sol
		exit(0)
	else:
		print w2
		sol = ''.join(test2)
		print sol
		exit(0)

s.append(None)


last = None
start = -1
end = -1

W = 0
for i in range(n+1):
	if s[i] != last:

		if end > start:
			for c in MAP:
				if c != s[start] and c != s[i]:
					break

			for j in range(start+1, end+1, 2):
				s[j] = c

			W += (end-start+1)/2


		start = i
		end = i


	else:
		end += 1


	last = s[i]



del s[-1]
sol = ''.join(s)

print W
print sol