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
Using python can you solve the prior task?

=====
Write me a Python code to print a single integer — the required minimum number of repaintings?
assistant
#Here is Python code to print a single integer — the required minimum number of repaintings.

"""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...