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:
def change(i, j, ch, strip):
    p = 0
    while i < j:
        if (p % 2):
            strip[i] = ch
        i += 1
        p += 1
        
n, k = map(int, raw_input().split())
strip = list(raw_input())

if k == 2:
    A = ['A' if not (i % 2) else 'B' for i in xrange(len(strip))]
    B = ['B' if not (i % 2) else 'A' for i in xrange(len(strip))]
    a, b = 0, 0
    for i in xrange(len(strip)):
        a += (strip[i] != A[i])
        b += (strip[i] != B[i])
    A, a = (A, a) if a < b else (B, b)
    print(str(a) + '\n' + ''.join(A))
else:
    ans = 0
    for i in xrange(len(strip)):
        j = i
        while j + 1 < len(strip) and strip[j] == strip[j + 1]:
            j += 1
        j += 1
        p = 0
        if j - i < 2:
            continue
        ans += (j - i) / 2
        if (j - i) % 2:
            ch = 'A' if ord(strip[i]) - 65 > 0 else 'B'
            change(i, j, ch, strip)
        else:
            if j == len(strip):
                ch = 'A' if ord(strip[i]) - 65 > 0 else 'B'
            else:
                if ord(strip[i]) - 65 > 0 and strip[j] != 'A':
                    ch = 'A'
                elif strip[j] == 'A' and strip[i] == 'B':
                    ch = 'C'
                elif strip[j] == 'A':
                    ch = 'B'
                elif strip[i] != 'A':
                    ch = 'A'
                else:
                    ch = 'B' if strip[j] != 'B' else 'C'
            change(i, j, ch, strip)
    print(ans)
    print(''.join(strip))