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

input = sys.stdin

N, K = map(int, input.readline().split())
S = input.readline().strip()

C = list(set(s for s in S))
if len(C) == 1:
	if C[0] != 'A':
		C.append('A')
	else:
		C.append('B')

C2 = {}
for c1 in C:
	for c2 in C:
		for c3 in C:
			if c1 != c3 and c2 != c3:
				C2[c1 + c2] = c3

C1 = {}
for c1 in C:
	for c2 in C:
		if c1 != c2:
			C1[c1] = c2

K = len(C)
if K == 2:
	O1 = [C[i % 2] for i in xrange(N)]
	O2 = [C[i % 2] for i in xrange(1, N + 1)]
	cnt1 = 0
	for i in xrange(N):
		if O1[i] != S[i]:
			cnt1 += 1
	cnt2 = 0
	for i in xrange(N):
		if O2[i] != S[i]:
			cnt2 += 1
	if cnt1 < cnt2:
		print cnt1
		print ''.join(O1)
	else:
		print cnt2
		print ''.join(O2)
else:
	R = [1] * N
	for i in xrange(1, N):
		if S[i] == S[i - 1]:
			R[i] = R[i - 1] + 1
	Z = [S[i] for i in xrange(N)]
	cnt = 0
	for i in xrange(1, N - 1):
		if R[i] % 2 == 0:
			Z[i] = C2[S[i - 1] + S[i + 1]]
			cnt += 1
	if R[N - 1] % 2 == 0:
		Z[N - 1] = C1[Z[N - 2]]
		cnt += 1

	print cnt
	print ''.join(Z)