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:
import bisect
import decimal
from decimal import Decimal
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq 
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate

# sys.setrecursionlimit(200000)
# mod = 10**9+7
# mod = 998244353
decimal.getcontext().prec = 46

def primeFactors(n): 
    prime = set()
    while n % 2 == 0: 
        prime.add(2)
        n = n//2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            prime.add(i)
            n = n//i 
    if n > 2: 
        prime.add(n)
    return list(prime)
    
def getFactors(n) : 
    factors = []
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n // i == i) : 
                factors.append(i)
            else : 
                factors.append(i)
                factors.append(n//i)
        i = i + 1
    return factors
    
def SieveOfEratosthenes(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    num = []
    for p in range(2, n+1): 
        if prime[p]: 
            num.append(p)
    return num

def lcm(a,b):
    return (a*b)//math.gcd(a,b)

def sort_dict(key_value):
    return sorted(key_value.items(), key = lambda kv:(kv[1], kv[0]))

def list_input():
    return list(map(int,input().split()))
    
def num_input():
    return map(int,input().split())
    
def string_list():
    return list(input())
    
def decimalToBinary(n):  
    return bin(n).replace("0b", "")  
    
def binaryToDecimal(n): 
    return int(n,2) 
    
def new_chr(a,b,alpha,k):
    for i in range(k):
        if alpha[i] != a and alpha[i] != b:
            return alpha[i]
        
def solve():
    n,k = num_input()
    s = input()
    if n == 1:
        print(0)
        print(s)
        return
    s = list(s)
    if k == 2:
        s1 = 'AB'*(n//2)
        s2 = 'BA'*(n//2)
        if n%2 != 0:
            s1 += 'A'
            s2 += 'B'
        c1 = c2 = 0
        for i in range(n):
            if s[i] != s1[i]:
                c1 += 1
            if s[i] != s2[i]:
                c2 += 1
        if c1 < c2:
            print(c1)
            print(s1)
        else:
            print(c2)
            print(s2)
    else:
        alpha = ['A']
        for i in range(1,26):
            alpha.append(chr(ord('A')+i))
        i = 0
        ans = 0
        while i < n-1:
            if s[i] == s[i+1]:
                count = 1
                j = i+1
                while j < n and s[i] == s[j]:
                    count += 1
                    if count%2 == 0:
                        if j+1 < n:
                            s[j] = new_chr(s[j],s[j+1],alpha,k)
                        else:
                            s[j] = new_chr(s[j],s[j],alpha,k)
                    j += 1
                ans += count//2
            else:
                i += 1
        print(ans)
        print(''.join(s))
            

#t = int(input())
t = 1
for _ in range(t):
    solve()