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:
n, k = map(int, input().split())
s = input()
b = []
c=[]
for j in s:
    b.append(j)
    c.append(j)
if n == 1:
    print(0)
    print(b[0])
elif n == 2:
    if b[0] == b[1]:
        print(1)
        print("AB")
    else:
        print(0)
        print("".join(b))

else:
    if k == 2:
        b[0]="A"
        j=1
        s=0
        while(j<n):
            if b[j-1]==b[j]:
                if b[j]=="A":
                    b[j]="B"
                else:
                    b[j]="A"
                s+=1
            j+=1
        p=0
        if c[0]=="B":
            s+=1
        else:
            p+=1
        c[0]="B"
        j=1
        while (j < n):
            if c[j - 1] == c[j]:
                if c[j] == "A":
                    c[j] = "B"
                else:
                    c[j] = "A"
                p += 1
            j += 1
        if p>s:
            print(s)
            print("".join(b))
        else:
            print(p)
            print("".join(c))






    else:
        j = 0
        s = 0
        while (j < (n - 1)):
            if j < (n - 2) and b[j] == b[j + 1] and b[j] == b[j + 2]:
                s += 1
                if (ord(b[j]) - 64) == k:
                    b[j + 1] = "A"
                else:
                    b[j + 1] = chr(ord(b[j]) + 1)

                j += 2
            elif j < (n - 2) and b[j] == b[j + 1] and b[j] != b[j + 2]:
                s += 1
                for p in range(65,65+k):
                    if ord(b[j])==p or ord(b[j+2])==p:
                        pass
                    else:
                        b[j+1]=chr(p)
                        break
                j += 2
            elif j == (n - 2) and b[j] == b[j + 1]:
                s += 1
                if (ord(b[j]) - 64) == k:
                    b[j + 1] = "A"
                else:
                    b[j + 1] = chr(ord(b[j]) + 1)
                j += 1
            elif b[j] != b[j + 1]:
                j += 1
        print(s)
        print("".join(b))