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:
"""Template for Python Competitive Programmers prepared by Mayank Chaudhary """

# to use the print and division function of Python3
from __future__ import division, print_function

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""use resource"""
# import resource
# resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])

"""for factorial"""

# def prepare_factorial():
#     fact = [1]
#     for i in range(1, 100005):
#         fact.append((fact[-1] * i) % mod)
#     ifact = [0] * 100005
#     ifact[100004] = pow(fact[100004], mod - 2, mod)
#     for i in range(100004, 0, -1):
#         ifact[i - 1] = (i * ifact[i]) % mod
#
#     return fact, ifact

"""uncomment next 4 lines while doing recursion based question"""
# import threading
# threading.stack_size(2**27)
import sys
# sys.setrecursionlimit(10000)


"""uncomment modules according to your need"""
# from bisect import bisect_left, bisect_right, insort
# import itertools
from math import floor, ceil, sqrt, degrees, atan, pi
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from collections import Counter, defaultdict, deque

'''
def modinv(n, p):
    return pow(n, p - 2, p)
'''


# def ncr(n, r,  fact, ifact):  # for using this uncomment the lines calculating fact and ifact
#     t = ((fact[n]) * (ifact[r] % mod)) % mod
#     return t



def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()


def GCD(x, y):
    while (y):
        x, y = y, x % y
    return x
#
# def lcm(x, y):
#     return (x*y)//(GCD(x, y))
#
# def get_xor(n):
#     return [n,1,n+1,0][n%4]


"""*******************************************************"""

def main():

    n,k = get_ints()
    string = input()

    if k==2:        # follow this easy case case 1: ABABABAB case 2 : BABABABABA

        store1 = ['A', 'B']
        make1 = [store1[i%2] for i in range(n)]
        store2 = ['B', 'A']
        make2 = [store2[i%2] for i in range(n)]

        count1 = count2 = 0
        # print(string)
        # print(store1)
        # print(store2)

        for i,j in zip(string, make1):
            if i!=j:
                count1 += 1

        for i,j in zip(string, make2):
            if i!=j:
                count2 += 1

        if count1 < count2 :
            print(count1)
            print(''.join(make1))
        else:
            print(count2)
            print(''.join(make2))

    else:                     # when k > 2, number of cases to handle

        store = [string[0]]
        count = [1]

        for i in range(1, n):
            if string[i]==store[-1]:
                count[-1] += 1
            else:
                store.append(string[i])
                count.append(1)

        length = len(store)

        result = []
        ans = 0
        # print(store)

        for i in range(length):

            if count[i]==1:
                result.append(store[i])
                continue

            elif count[i]&1:                     # case for odd 2m+1 ---> change m
                ans += count[i]//2
                m = 0
                while chr(65 + m) ==store[i]:
                    m += 1
                pick = [store[i], chr(65 + m)]
                make = [pick[i%2] for i in range(count[i])]
                result.extend(make)

            else:                               # case for even 2m ----> m
                ans += count[i]//2
                if i==length-1:    # last hai right mekuch nhi

                    m = 0
                    while chr(65 + m) ==store[i]:
                        m += 1

                    pick = [store[i], chr(65 + m)]
                    make = [pick[i % 2] for i in range(count[i])]
                    result.extend(make)
                else:
                    # print(store[i], store[i+1])
                    m = 0
                    while chr(65 + m) == store[i+1] or chr(65 + m)==store[i]:
                        m += 1

                    pick = [store[i], chr(65 + m)]
                    make = [pick[i % 2] for i in range(count[i])]
                    result.extend(make)


        print(ans)
        print(''.join(result))












""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip

    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192


class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda: self.buffer.read().decode('ascii')
            self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

""" main function"""

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()