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 made by : https://codeforces.com/profile/c1729 , github repo : https://github.com/cheran-senthil/PyRival"
from __future__ import division, print_function
import bisect
import math
import itertools
import sys
from atexit import register

if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

def main():
    n,k=map(int,input().split())
    l1=list(input())
    count=0
    if k!=2:
        for i in range(n-1):
            if l1[i]==l1[i+1]:
                count+=1
                if i!=n-2:
                    if l1[i+1]==l1[i+2]:
                        l1[i+1]=chr((ord(l1[i+1])-64)%k+65)
                    else :
                        j=0
                        while j==(ord(l1[i])-65) or j==(ord(l1[i+2])-65):
                            j+=1
                        l1[i+1]=chr(j+65)
                else :
                    l1[i+1]=chr((ord(l1[i+1])-64)%k+65)
        print(count)
        print(''.join(l1))
    else :
        c1=0
        c2=0
        ans1=[]
        ans2=[]
        for i in range(n):
            if i%2==0:
                ans1.append('A')
                ans2.append('B')
            else :
                ans1.append('B')
                ans2.append('A')
            if ans1[i]!=l1[i]:
                c1+=1
            if ans2[i]!=l1[i]:
                c2+=1
        if c1>c2:
            print(c2)
            print(''.join(ans2))
        else :
            print(c1)
            print(''.join(ans1))
            
if __name__ == '__main__':
    sync_with_stdio(False)
    main()