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:
from sys import stdin,stdout
nmbr=lambda:int(stdin.readline())
lst = lambda: list(map(int,stdin.readline().split()))
PI=float('inf')
for _ in range(1):#nmbr()):
    n,k=lst()
    s=input()
    dp=[[0 for i in range(k)] for j in range(n)]
    mn=smn=0
    for i in range(k):
        dp[0][i]=1
    dp[0][ord(s[0])-65]=0
    mn = smn = PI
    p1 = p2 = -1
    for j in range(k):
        if dp[0][j] <= mn:
            smn = mn
            p2 = p1
            p1 = j
            mn = dp[0][j]
        elif dp[0][j] < smn:
            smn = dp[0][j]
            p2 = j
    # print(mn,smn,p1,p2)
    for i in range(1,n):
        mn1=smn1=PI
        pp1=pp2=-1
        for j in range(k):
            if j==p1:
                dp[i][j]=int(ord(s[i])!=(j+65))+dp[i-1][p2]
            else:
                dp[i][j]=int(ord(s[i])!=(j+65))+dp[i-1][p1]
            if dp[i][j]<=mn1:
                smn1=mn1
                pp2=pp1
                pp1=j
                mn1=dp[i][j]
            elif dp[i][j]<smn1:
                smn1=dp[i][j]
                pp2=j
        mn,smn=mn1,smn1
        p1,p2=pp1,pp2
        # print(mn,smn)
    ans=[]
    cur=mn
    prev=-1
    for i in range(n-1,-1,-1):
        if prev!=-1:dp[i][prev]=n+1
        for j in range(k):
            if dp[i][j]==cur:
                pos=j
                break
        ans+=[pos]
        if ord(s[i])!=(pos+65):
            cur-=1
        prev=pos
    # mn=0
    # print(ans)
    # ans.reverse()
    # print(ans)
    # for c,c1 in zip(ans,s):
    #     mn+=int((chr(c+65)!=c1))
    print(mn)
    # print(dp)
    for ch in ans[::-1]:stdout.write(chr(ch+65))