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 f(s, i, flag):
    if s[i] == s[i+1] or s[i] == s[i-1]:
        if not flag and i < n - 2 and s[i] == s[i+2]:
            f(s, i + 1, True)
        elif s[i] >= 'C':
            s[i] = 'A'
            f(s, i, True)
        else:
            s[i] = chr(ord(s[i]) + 1)
            f(s, i, True)

n, k = map(int, raw_input().split())
s = list(raw_input())
c = 0

if n == 1:
    pass
elif k == 2:
    ss = list(s)
    c1 = 0
    c2 = 0
    for i in xrange(n):
        if s[i] != chr(ord('A') + i % 2):
            s[i] = chr(ord('A') + i % 2)
            c1 += 1
        if ss[i] != chr(ord('B') - i % 2):
            ss[i] = chr(ord('B') - i % 2)
            c2 += 1
    if c1 < c2:
        c = c1
    else:
        c = c2
        s = ss
else:
    for i in xrange(0, n - 1):
        if s[i] == s[i+1]:
            f(s, i, False)
            c += 1

print c
print "".join(s)