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:
n, k = map(int, raw_input().split())
s = raw_input()
i = 0
total = 0
r = list(s)
r_a = list(s)
r_b = list(s)
if k == 2:
	c_a = 0
	c_b = 0
	for z in range(len(s)):
		if z % 2 == 0:
			if s[z] == "B":
				c_a += 1
			else:
				c_b += 1
			r_a[z] = "A"
			r_b[z] = "B"
		else:
			if s[z] == "A":
				c_a += 1
			else:
				c_b += 1
			r_a[z] = "B"
			r_b[z] = "A"
	if c_a <= c_b:
		print c_a
		print "".join(r_a)
	else:
		print c_b
		print "".join(r_b)
else:
	while i < len(s):
		#print i
		j = i + 1
		while j < len(s):
			if s[j] == s[i]:
				j += 1
			else:
				break
		l = j - i
		#print i, j, j - i
		if l >= 2:
			todo = l/2
			total += l/2
			x = i + 1
			sel = "A"
			while sel == s[i] or (l%2 == 0 and i+l < len(s) and sel == s[i+l]):
				sel = str(chr(ord(sel) + 1))
			while todo != 0:
				r[x] = sel
				x += 2
				todo -= 1
			
		i += l
	print total
	print "".join(r)