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 string


def stripped_line():
    return raw_input().strip()


def read_ints():
    return map(int, stripped_line().split())


def g(a, b, count):
    colors = string.ascii_uppercase[:count]
    for c in colors:
        if c not in [a, b]:
            return c


def d(a, b):
    ''' count diffs '''
    r, i = 0, 0
    n = len(a)
    while i < n:
        if a[i] != b[i]:
            r += 1
        i += 1
    return r


n, k = read_ints()
s = list(stripped_line())

a = 0
i = 0
result = []
if n == 1:
    print 0
    print "".join(s)
    exit(0)

if k == 2:
    first = "AB" * (n / 2 + 1)
    second = "BA" * (n / 2 + 1)
    fc, sc = d(first[:n], "".join(s)), d(second[:n], "".join(s))
    if fc <= sc:
        print fc
        print first[:n]
    else:
        print sc
        print second[:n]
else:
    parts = []
    parts.append([s[0]])
    for l in s[1:]:
        if parts[-1][-1] == l:
            parts[-1].append(l)
        else:
            parts.append([l])

    for pk, part in enumerate(parts):
        if len(part) == 1:
            result.append(part[0])
        else:
            next_color = part[0]
            if pk + 1 < len(parts):
                next_color = parts[pk + 1][0]
            for kp, p in enumerate(part):
                if (kp + 1) % 2 == 0:
                    z = g(p, next_color, k)
                    result.append(z)
                    a += 1
                else:
                    result.append(p)

    print a
    print "".join(result)