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 PYTHON3):

Solution:
from collections import defaultdict,OrderedDict,Counter
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
# import numpy as np
from queue import Queue
from statistics import median
from math import gcd,sqrt,floor,factorial,ceil,log2,log10
import copy
from copy import deepcopy
import sys
sys.setrecursionlimit(10**7)
import math
import os
import bisect
import collections
mod=pow(10,9)+7

def ncr(n, r, p=mod):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
            p - 2, p)) % p
# input=stdin.readline
# print=stdout.write
inf=float("inf")
adj=defaultdict(set)
visited=defaultdict(int)
def addedge(a,b):
    adj[a].add(b)
    adj[b].add(a)
def bfs(v):
    q=Queue()
    q.put(v)
    visited[v]=1
    while q.qsize()>0:
        s=q.get_nowait()
        print(s)
        for i in adj[s]:
            if visited[i]==0:
                q.put(i)
                visited[i]=1
def dfs(v,visited):
    if visited[v]==1:
        return;
    visited[v]=1

    print(v)
    for i in adj[v]:
        dfs(i,visited)
# a9=pow(10,6)+10
# prime = [True for i in range(a9 + 1)]
# def SieveOfEratosthenes(n):
#     p = 2
#     while (p * p <= n):
#         if (prime[p] == True):
#             for i in range(p * p, n + 1, p):
#                 prime[i] = False
#         p += 1
def get_list():
    return list(map(int,input().split()))
def get_str_list():
    return list(input())
def get_map():
    return map(int,input().split())
def get_int():
    return int(input())
def powof2(a):
    if a&(a-1)==0:
        return 1;
    return 0;
# t=int(input())
def chr_to_int(a):
    return ord(a)-ord('a')+1
store=defaultdict(int)
for i in range(ord('A'),ord('Z')+1):
    store[chr(i)]+=1

def three_same(l):

    for i in range(1,n-1):
        if l[i-1]==l[i]==l[i+1] and store[l[i-1]] and store[l[i]] and store[l[i+1]]:

            dict[i]=1;
            l[i]=chr_to_int(l[i])
def two_same(l):
    for i in range(1,n):
        if l[i-1]==l[i] and store[l[i]] and store[l[i-1]]:
            dict[i]=1
def diff(a,b):
    count=0;
    for i in range(n):
        if a[i]!=b[i]:
            count+=1
    return count
t=1
for i in range(t):
    n,k=get_map();

    l=get_str_list()
    if k==2:
        m1=[]
        m2=[]
        for i in range(n):
            if i%2==0:
                m1.append('A')
                m2.append('B')
            else:
                m2.append('A')
                m1.append('B')
        diff1=diff(l,m1)
        diff2=diff(l,m2)
        if diff1<=diff2:
            print(diff1)
            print("".join(m1))
        else:
            print(diff2)
            print("".join(m2))
        continue;
    dict=defaultdict(int)
    three_same(l)
    two_same(l)
    
    for i in range(n):
        if i in dict:
            if i==0:
                if 'A' in l[1]:
                    l[i]='B'
                else:
                    l[i]='A'
            elif i==n-1:
                if 'A' in l[n-2]:
                    l[i]='B'
                else:
                    l[i]='A'
            else:
                if 'A' in l[i-1] + l[i+1]:
                    
                    if 'B' in l[i-1] + l[i+1]:
                        l[i]='C'
                    else:
                        l[i]='B'
                else:
                    l[i]='A'

    print(len(dict))
    print("".join(l))