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:
 ######      ###      #######    #######    ##      #     #####        ###     ##### 
 #     #    #   #          #        #       # #     #    #     #      #   #     ###  
 #     #   #     #        #         #       #  #    #   #       #    #     #    ###  
 ######   #########      #          #       #   #   #   #           #########    #   
 ######   #########     #           #       #    #  #   #           #########    #   
 #     #  #       #    #            #       #     # #   #    ####   #       #    #   
 #     #  #       #   #             #       #      ##   #    #  #   #       #        
 ######   #       #  #######     #######    #       #    #####  #   #       #    #   
 
from __future__ import print_function # for PyPy2
from itertools import permutations as perm
# from fractions import Fraction
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
 
g   = lambda : stdin.readline().strip()
gl  = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1e9)+7
inf = float("inf")

n, k = gil()
s = [ord(ch)-65 for ch in g()]
# print(s)
dp = [[1 for _ in range(n)] for _ in range(k)]

dp[s[0]][0] = 0

# for r in dp:
# 	print(r)

for j in range(1, n):
	mi = min(range(k), key=lambda x:dp[x][j-1])
	mi2 = min(range(k), key=lambda x: dp[x][j-1] if x!=mi else inf)
	dp[s[j]][j] = 0
	i = 0
	val = dp[mi][j-1]
	while i < k:
		if i != mi:
			dp[i][j] += val
		else:
			dp[mi][j] += dp[mi2][j-1]
		i += 1

# for r in dp:
# 	print(*r)

idx = min(range(k), key=lambda x: dp[x][-1])
print(dp[idx][-1])
ans = [chr(idx+65)]
i = n-2
while i >= 0:
	idx = min(range(k), key=lambda x: dp[x][i] if x != idx else inf)
	ans.append(chr(idx+65))
	i -= 1
ans.reverse()
print(''.join(ans))