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 collections
import functools
import itertools
import math
import operator
import re
import sys


def func(lst, k):
    res = lst[:]
    cnt = 0
    for i in xrange(1, len(lst)):
        if res[i] == res[i - 1]:
            for x in xrange(k):
                tmp = chr(ord('A') + x)
                if tmp != res[i - 1] and (i == len(lst) - 1 or i < len(lst) - 1 and tmp != res[i + 1]):
                    res[i] = tmp
                    break
            else:
                for x in xrange(k):
                    tmp = chr(ord('A') + x)
                    if tmp != res[i - 1]:
                        res[i] = tmp
                        break
            cnt += 1
    return cnt, res


def main():
    n, k = map(int, raw_input().split())
    s = raw_input()
    a = list(s)
    if k == 2:
        p1 = p2 = 0
        q1 = ['A' if i % 2 == 0 else 'B' for i in xrange(n)]
        q2 = ['A' if i % 2 == 1 else 'B' for i in xrange(n)]
        p1 = sum(1 if q1[i] != a[i] else 0 for i in xrange(n))
        p2 = sum(1 if q2[i] != a[i] else 0 for i in xrange(n))
    else:
        p1, q1 = func(a, k)
        p2, q2 = func(list(reversed(a)), k)
        q2.reverse()
    res = min((p1, q1), (p2, q2))
    print res[0]
    print ''.join(res[1])


if __name__ == '__main__':
    main()