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 os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
#######################################
n,k=map(int,input().split())
s=input()
if k==2:
    s1='AB'*(len(s)//2)
    if len(s)%2:
        s1+='A'
    s2='BA'*(len(s)//2)
    if len(s)%2:
        s2+='B'
    ans1=0
    ans2=0
    for i in range(len(s)):
        if s1[i]!=s[i]:
            ans1+=1
        if s2[i]!=s[i]:
            ans2+=1
    if ans1<ans2:
        print(ans1)
        print(s1)
    else:
        print(ans2)
        print(s2)
else:
    s1=[]
    ans=0
    l=[]
    i=0
    while i<len(s):
        if i==len(s)-1:
            l.append([1,len(s)-1,len(s)-1])
            break
        if s[i]==s[i+1]:
            c=1
            j=i
            while s[i]==s[i+1]:
                c+=1
                i+=1
                if i==len(s)-1:
                    break
            l.append([c,j,i])
            i+=1
        else:
            l.append([1,i,i])
            i+=1
    for j in l:
        if j[0]==1:
            s1.append(s[j[1]])
        else:
            a=0
            for p in range(j[1],j[2]+1):
                if a==0:
                    s1.append(s[p])
                    a^=1
                else:
                    for q in range(k):
                        if chr(65+q)!=s[p]:
                            s1.append(chr(65+q))
                            break
                    ans+=1
                    a^=1
            if j[0]%2==0:
                if j[2]!=len(s)-1:
                    if s1[j[2]]==s[j[2]+1]:
                        for p  in range(k):
                            if chr(65+p)!=s[j[2]+1] and chr(65+p)!=s[j[2]]:
                                s1[j[2]]=chr(65+p)
                                break
    print(ans)
    print(''.join(s1))