human
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
# Leg Give me a Python program to print a single integer — the required minimum number of repaintings?
assistant
#Here is Python program to print a single integer — the required minimum number of repaintings.
ends Always Come Up with Solution
# Author: Manvir Singh

import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction
from heapq import *
from random import randint

def main():
    n,k=map(int,input().split())
    a=list(input().rstrip())
    if k>2:
        ans,s=0,"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[:k]
        for i in range(n-1):
            if a[i]==a[i+1]:
                for j in s:
                    if j!=a[i] and (i+2<n and j!=a[i+2] or i==n-2):
                        a[i+1]=j
                        ans+=1
                        break
        print(ans)
        print("".join(a))
    else:
        s1,s2,x,y="AB"*(n//2)+"A"*(n%2),"BA"*(n//2)+"B"*(n%2),0,0
        for i in range(n):
            if a[i]!=s1[i]:
                x+=1
            if a[i]!=s2[i]:
                y+=1
        if x>y:
            print(y)
            print(s2)
        else:
            print(x)
            print(s1)

# region fastio
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b),...