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:
import sys
def rs():
    return sys.stdin.readline().strip()
def ri():
    return int(sys.stdin.readline().strip())
def ras():
    return sys.stdin.readline().strip().split()
def rai():
    return map(int,sys.stdin.readline().strip().split())
def main():
    n,k = rai()
    ss = list(rs())
    if n==1:
        return '0' + '\n' + ''.join(ss)
    count = 0

    arr = ['A','B','C','D']
    gel = lambda x,y: [i for i in arr if i!=x and i!=y][0]



    if k==2:
        t1,t2 ='',''
        for i in range(n):
            if i%2:
                t1+='A'
                t2+='B'
            else:
                t1+='B'
                t2+='A'

        c1,c2 = 0,0

        for i in range(n):
            if t1[i]!=ss[i]:
                c1+=1
            if t2[i]!=ss[i]:
                c2+=1
        if c1<c2:
            return str(c1) + '\n' + t1
        else:
            return str(c2) + '\n' + t2


    for i in xrange(1,n-1):
        if ss[i]==ss[i-1]:
            ss[i]=gel(ss[i-1], ss[i+1])
            count+=1
    if ss[n-1] == ss[n-2]:
        count+=1
        ss[n-1] = gel(ss[n-2], ss[n-2])
    return str(count) + '\n' + ''.join(ss)

if __name__ == "__main__":
    print main()