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:
import sys
from math import sqrt, gcd, ceil, log
# from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
# from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))


def main():
	n, k = read()
	s = input().strip()+chr(k+64)
	if k == 2:
		t1 = ("AB"*(n//2 + 1))[:n]
		t2 = ("BA"*(n//2 + 1))[:n]
		dif1 = dif2 = 0
		for i in range(n):
			dif1 += t1[i] != s[i]
			dif2 += t2[i] != s[i]
		if dif1 > dif2:
			print(dif2)
			print(t2)
		else:
			print(dif1)
			print(t1)
		exit()
	ans = s[0]
	i = 1
	alphs = {i-65: chr(i)  for i in range(65, 65+k)}
	# print(alphs)
	l = 0
	while i < len(s)-1:
		if ans[-1] == s[i]:
			ind = 0
			while ind < k and ind == ord(ans[-1])-65 or ind == ord(s[i+1])-65:
				ind += 1
				ind %= k

			ans += alphs[ind%k]
			l += 1
		else:
			ans += s[i]
		i += 1
	print(l)
	print(ans)




if __name__ == "__main__":
	main()