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

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Complete search

Greedy algorithms
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
(n, k) = map(int, input().split())
s = input()
if k == 2:
	sol1 = [s[i] for i in range(n)]
	ans1 = 0
	for i in range(n):
		if i % 2 == 0 and sol1[i] == 'B':
			ans1 += 1
			sol1[i] = 'A'
		elif i % 2 != 0 and sol1[i] == 'A':
			ans1 += 1
			sol1[i] = 'B'
	sol2 = [s[i] for i in range(n)]
	ans2 = 0
	for i in range(n):
		if i % 2 == 0 and sol2[i] == 'A':
			ans2 += 1
			sol2[i] = 'B'
		elif i % 2 != 0 and sol2[i] == 'B':
			ans2 += 1
			sol2[i] = 'A'
	if ans1 <= ans2:
		print(ans1)
		print(''.join((str(x) for x in sol1)))
	else:
		print(ans2)
		print(''.join((str(x) for x in sol2)))
else:
	s = [s[i] for i in range(n)]
	ans = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans += 1
			x = chr((ord(s[i - 1]) - 65 + 1) % k + 65)
			if i == n - 1 or s[i + 1] != x:
				s[i] = x
			else:
				y = chr((ord(s[i - 1]) - 65 + 1 + 1) % k + 65)
				s[i] = y
	print(ans)
	print(''.join((str(x) for x in s)))


(n, k) = map(int, input().split())
s = input()
if k == 2:
	x = 'A'
	y = 'B'
	for i in range(1, n):
		if x[-1] == 'A':
			x += 'B'
		else:
			x += 'A'
		if y[-1] == 'A':
			y += 'B'
		else:
			y += 'A'
	p1 = 0
	p2 = 0
	for i in range(n):
		if x[i] != s[i]:
			p1 += 1
		if y[i] != s[i]:
			p2 += 1
	if p1 >= p2:
		print(p2)
		print(y)
	else:
		print(p1)
		print(x)
	exit()
ans = s[0]
colors = []
pts = 0
for i in range(k):
	colors.append(chr(i + 65))
for i in range(1, n):
	x = s[i]
	if x != ans[-1]:
		ans += x
	elif k == 2 or i == n - 1:
		for y in colors:
			if y != x:
				ans += y
				pts += 1
				break
	else:
		z = s[i + 1]
		for y in colors:
			if y != x and y != z:
				ans += y
				pts += 1
				break
print(pts)
print(ans)


def main():
	(n, k) = map(int, input().split())
	s = list(input())
	if k > 2:
		ans = 0
		for (idx, i) in enumerate(s):
			if idx == 0:
				continue
			if s[idx] == s[idx - 1]:
				for j in range(k):
					c = chr(65 + j)
					if s[idx] == c:
						continue
					elif idx + 1 < n:
						if s[idx + 1] == c:
							continue
					s[idx] = c
					ans += 1
					break
		print(ans)
		print(''.join(s))
	else:
		pat1 = 'AB' * n
		ans1 = 0
		for (idx, i) in enumerate(s):
			if i != pat1[idx]:
				ans1 += 1
		pat2 = 'BA' * n
		ans2 = 0
		for (idx, i) in enumerate(s):
			if i != pat2[idx]:
				ans2 += 1
		if ans1 <= ans2:
			print(ans1)
			print(pat1[:n])
		else:
			print(ans2)
			print(pat2[:n])
	return
main()


(n, k) = map(int, input().split())
s = [i for i in input()]
d = {i: chr(65 + i) for i in range(k)}
ct = 0
if k == 2:
	a1 = []
	a2 = []
	for i in range(n):
		a1.append(d[i % 2])
		a2.append(d[(1 + i) % 2])
	ct1 = 0
	ct2 = 0
	for i in range(n):
		if s[i] != a1[i]:
			ct1 += 1
		if s[i] != a2[i]:
			ct2 += 1
	if ct2 < ct1:
		print(ct2)
		print(''.join(a2))
	else:
		print(ct1)
		print(''.join(a1))
else:
	for i in range(1, n):
		if s[i] == s[i - 1]:
			s[i] = ' '
			ct += 1
	for i in range(1, n - 1):
		if s[i] == ' ':
			for j in range(k):
				if s[i - 1] != d[j] and s[i + 1] != d[j]:
					s[i] = d[j]
					break
	if s[-1] == ' ':
		for j in range(k):
			if s[-2] != d[j]:
				s[-1] = d[j]
				break
	print(ct)
	print(''.join(s))


(n, k) = map(int, input().strip().split())
s = list(input())
options = [chr(ord('A') + i) for i in range(k)]
ans = 0
if k == 2:
	ans1 = ['A' if i % 2 == 0 else 'B' for i in range(n)]
	diff1 = 0
	for i in range(n):
		if s[i] != ans1[i]:
			diff1 += 1
	if diff1 < n - diff1:
		print(diff1)
		print(''.join(ans1))
	else:
		print(n - diff1)
		print('B' + ''.join(ans1[:-1]))
else:
	for i in range(1, n - 1):
		if s[i] == s[i - 1]:
			ans += 1
			for j in options:
				if j != s[i - 1] and j != s[i + 1]:
					s[i] = j
					break
	if n > 1 and s[-2] == s[-1]:
		ans += 1
		s[-1] = options[0] if options[0] != s[-2] else options[1]
	print(ans)
	print(''.join(s))


from sys import stdin
(n, k) = map(int, stdin.readline().split())
s = stdin.readline().strip()
cand = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
cnt = 0
if k == 2:
	cmps = ('AB' * ((n + 1) // 2))[:n]
	for i in range(n):
		if s[i] != cmps[i]:
			cnt += 1
	if cnt < n - cnt:
		print(cnt)
		print(cmps)
	else:
		print(n - cnt)
		print(''.join(('BA' * ((n + 1) // 2))[:n]))
else:
	l = 0
	r = 1
	rs = list(s)
	pch = rs[0]
	for i in range(1, n):
		if rs[i] == pch:
			r += 1
		else:
			d = r - l
			if d > 1:
				if d % 2:
					l += 1
				for j in range(l, r, 2):
					p = 0
					while p < k and (j > 0 and rs[j - 1] == cand[p] or (j < n - 1 and rs[j + 1] == cand[p])):
						p += 1
					rs[j] = cand[p]
					cnt += 1
			pch = rs[i]
			l = r
			r = l + 1
	d = r - l
	if d > 1:
		if d % 2:
			l += 1
		for j in range(l, r, 2):
			p = 0
			while p < k and (j > 0 and rs[j - 1] == cand[p] or (j < n - 1 and rs[j + 1] == cand[p])):
				p += 1
			rs[j] = cand[p]
			cnt += 1
	print(cnt)
	print(''.join(rs))


import os
import sys
from io import BytesIO, IOBase
from math import factorial

def main():
	(n, k) = map(int, input().split())
	a = list(input())
	cnt = 0
	if k <= 2:
		x = 'AB' * n
		y = 'BA' * n
		(x_val, y_val) = (0, 0)
		for i in range(n):
			if x[i] != a[i]:
				x_val += 1
			if y[i] != a[i]:
				y_val += 1
		if x_val > y_val:
			print(y_val)
			print(y[:n])
		else:
			print(x_val)
			print(x[:n])
	else:
		for i in range(1, n):
			if a[i - 1] == a[i]:
				cnt += 1
				a[i] = list(set('ABC') - set(a[i:i + 2]))[0]
		print(cnt)
		print(''.join(a))
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
PI = float('inf')
for _ in range(1):
	(n, k) = lst()
	s = input()
	dp = [[0 for i in range(k)] for j in range(n)]
	mn = smn = 0
	for i in range(k):
		dp[0][i] = 1
	dp[0][ord(s[0]) - 65] = 0
	mn = smn = PI
	p1 = p2 = -1
	for j in range(k):
		if dp[0][j] <= mn:
			smn = mn
			p2 = p1
			p1 = j
			mn = dp[0][j]
		elif dp[0][j] < smn:
			smn = dp[0][j]
			p2 = j
	for i in range(1, n):
		mn1 = smn1 = PI
		pp1 = pp2 = -1
		for j in range(k):
			if j == p1:
				dp[i][j] = int(ord(s[i]) != j + 65) + dp[i - 1][p2]
			else:
				dp[i][j] = int(ord(s[i]) != j + 65) + dp[i - 1][p1]
			if dp[i][j] <= mn1:
				smn1 = mn1
				pp2 = pp1
				pp1 = j
				mn1 = dp[i][j]
			elif dp[i][j] < smn1:
				smn1 = dp[i][j]
				pp2 = j
		(mn, smn) = (mn1, smn1)
		(p1, p2) = (pp1, pp2)
	ans = []
	cur = mn
	prev = -1
	for i in range(n - 1, -1, -1):
		if prev != -1:
			dp[i][prev] = n + 1
		for j in range(k):
			if dp[i][j] == cur:
				pos = j
				break
		ans += [pos]
		if ord(s[i]) != pos + 65:
			cur -= 1
		prev = pos
	print(mn)
	for ch in ans[::-1]:
		stdout.write(chr(ch + 65))


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(100000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	(n, k) = mi()
	s = list(si())
	(a, b) = (0, 0)
	if k == 2:
		for i in range(n):
			if i % 2 == 0:
				if s[i] == 'A':
					a += 1
				else:
					b += 1
			elif s[i] == 'B':
				a += 1
			else:
				b += 1
		print(min(a, b))
		x = ''
		for i in range(n):
			if a < b:
				if i % 2 == 0:
					x += 'B'
				else:
					x += 'A'
			elif i % 2 == 0:
				x += 'A'
			else:
				x += 'B'
		print(x)
	else:
		abd = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
		cnt = 0
		for i in range(1, n):
			if s[i] == s[i - 1]:
				c = 0
				while s[i - 1] == abd[c] or (i + 1 < n and s[i + 1] == abd[c]):
					c += 1
				s[i] = abd[c]
				cnt += 1
		print(cnt)
		print(''.join(s))
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
input = stdin.readline

def put():
	return map(int, input().split())
(n, k) = put()
s = [ord(i) - ord('A') for i in list(input())]
ans = []
dp = [0] * k
ans.append(dp)
a = b = 0
for i in range(n):
	tmp = []
	(first, second) = (n + 1, n + 1)
	for j in range(k):
		if dp[j] == a:
			y = b
		else:
			y = a
		x = y + (0 if s[i] == j else 1)
		if first > x:
			second = first
			first = x
		elif second > x:
			second = x
			pass
		tmp.append(x)
	(a, b) = (first, second)
	dp = tmp
	ans.append(tmp)
l = []
x = min(dp)
prev = -1
for i in range(n, 0, -1):
	if prev != -1:
		ans[i][prev] = n + 1
	a = ans[i].index(x)
	l.append(chr(a + ord('A')))
	if s[i - 1] != a:
		x -= 1
	prev = a
print(min(dp))
y = ''.join(l[::-1])
print(y)


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
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
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)

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

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'
			elif '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))


(n, k) = list(map(int, input().split()))
a = [i for i in input()]
b = 0
if k == 2:
	for i in range(n):
		if a[i] != 'AB'[i % 2]:
			b += 1
	if b < n - b:
		print(b)
		print('AB' * (n // 2) + 'A' * (n % 2))
	else:
		print(n - b)
		print('BA' * (n // 2) + 'B' * (n % 2))
else:
	for i in range(1, n):
		if a[i] == a[i - 1]:
			for j in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[:k]:
				if j != a[i - 1] and (i == n - 1 or j != a[i + 1]):
					a[i] = j
					b += 1
					break
	print(b)
	print(''.join(a))


(n, k) = map(int, input().split())
p = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[:k] + 'A'
p = {p[i]: p[i + 1] for i in range(k)}
if k == 2:
	t = input()
	(u, v) = ('AB' * (n // 2) + 'A' * (n % 2), 'BA' * (n // 2) + 'B' * (n % 2))
	(x, y) = (sum((int(u[i] != t[i]) for i in range(n))), sum((int(v[i] != t[i]) for i in range(n))))
	if x < y:
		print(x)
		print(u)
	else:
		print(y)
		print(v)
else:
	(t, s) = (list(input()), 0)
	for i in range(1, n):
		if t[i] == t[i - 1]:
			t[i] = p[t[i]]
			if i + 1 < n and t[i] == t[i + 1]:
				t[i] = p[t[i]]
			s += 1
	print(s)
	print(''.join(t))


(n, k) = map(int, input().split())
if k == 2:
	(ab, ba) = ('AB' * (n // 2) + 'A' * (n % 2), 'BA' * (n // 2) + 'B' * (n % 2))
	(ab_c, ba_c) = (0, 0)
	old = input().strip()
	for i in range(n):
		ab_c += old[i] != ab[i]
		ba_c += old[i] != ba[i]
	if ab_c < ba_c:
		print(ab_c)
		print(ab)
	else:
		print(ba_c)
		print(ba)
else:
	(old, req, avail) = ([char for char in input().strip()], 0, 'ABCDEFGHIJKLMNOPQRSTUVWXYZA')
	for i in range(1, n):
		if old[i] == old[i - 1]:
			old[i] = avail[(avail.find(old[i - 1]) + 1) % k]
			if i != n - 1 and old[i] == old[i + 1]:
				old[i] = avail[(avail.find(old[i]) + 1) % k]
			req += 1
	print(req)
	print(''.join(old))


(n, k) = map(int, input().split())
s = input()
a = s
s = []
for i in range(len(a)):
	s.append(a[i])
prev = 0
alphs = []
ans = 0
for i in range(k):
	alphs.append(chr(ord('A') + i))
if k == 2:
	f = []
	sec = []
	t = 0
	for i in range(n):
		f.append(chr(ord('A') + t))
		sec.append(chr(ord('A') + (t + 1) % 2))
		t ^= 1
	ans1 = 0
	ans2 = 0
	for i in range(n):
		if s[i] != f[i]:
			ans1 += 1
		if s[i] != sec[i]:
			ans2 += 1
	if ans1 <= ans2:
		print(ans1)
		for i in f:
			print(i, end='')
	else:
		print(ans2)
		for i in sec:
			print(i, end='')
else:
	for i in range(1, n):
		if s[i] != s[prev]:
			if i - prev > 1:
				if (i - prev) % 2:
					ans += (i - prev) // 2
					t = 0
					put = ''
					for j in alphs:
						if j != s[prev]:
							put = j
							break
					for j in range(prev, i):
						if t % 2:
							s[j] = put
						t += 1
				else:
					end = ''
					other = ''
					for j in alphs:
						if j != s[prev] and j != s[i]:
							end = j
							break
					for j in alphs:
						if j != s[prev] and j != end:
							other = j
							break
					s[i - 1] = end
					ans += 1
					t = 0
					for j in range(i - 2, prev - 1, -1):
						if t % 2:
							s[j] = other
							ans += 1
						t += 1
			prev = i
	i = n - 1
	for i in range(n - 1, -1, -1):
		if s[i] != s[n - 1]:
			prev = i + 1
			break
	i = n - 1
	if i - prev > 0:
		if (i - prev + 1) % 2:
			ans += (i - prev + 1) // 2
			t = 0
			put = ''
			for j in alphs:
				if j != s[i]:
					put = j
					break
			for j in range(prev, i + 1):
				if t % 2:
					s[j] = put
				t += 1
		else:
			other = ''
			for j in alphs:
				if j != s[prev]:
					other = j
					break
			t = 0
			for j in range(i, prev - 1, -1):
				if t % 2 == 0:
					s[j] = other
					ans += 1
				t += 1
	print(ans)
	for i in s:
		print(i, end='')


(n, k) = map(int, input().split())
s = list(input())
if n == 1:
	print(0)
	print(s[0])
	exit()
if k == 2:
	(a, b) = ('A', 'B')
	(x, y) = (0, 0)
	for (i, item) in enumerate(s):
		if i % 2:
			if item == 'A':
				x += 1
			else:
				y += 1
		elif item == 'B':
			x += 1
		else:
			y += 1
	if x > y:
		print(y)
		print('BA' * (n // 2) + 'B' * (n % 2))
	else:
		print(x)
		print('AB' * (n // 2) + 'A' * (n % 2))
else:
	(a, b, c) = ('A', 'B', 'C')
	ans = 0
	for i in range(1, n - 1):
		if s[i] == s[i - 1]:
			st = set([s[i - 1], s[i + 1]])
			if a not in st:
				s[i] = a
				ans += 1
			elif b not in st:
				s[i] = b
				ans += 1
			else:
				s[i] = c
				ans += 1
	if s[-1] == s[-2]:
		ans += 1
		if s[-2] == a:
			s[-1] = b
		else:
			s[-1] = a
	print(ans)
	print(*s, sep='')


import sys
from math import sqrt, gcd, ceil, log
from collections import defaultdict, Counter, deque
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))

def main():
	(n, k) = read()
	s = input().strip() + chr(k + 64)
	if k == 2:
		t1 = ('AB' * (n // 2 + 1))[:n]
		t2 = ('BA' * (n // 2 + 1))[:n]
		dif1 = dif2 = 0
		for i in range(n):
			dif1 += t1[i] != s[i]
			dif2 += t2[i] != s[i]
		if dif1 > dif2:
			print(dif2)
			print(t2)
		else:
			print(dif1)
			print(t1)
		exit()
	ans = [s[0]]
	i = 1
	alphs = {i - 65: chr(i) for i in range(65, 65 + k)}
	l = 0
	while i < len(s) - 1:
		if ans[-1] == s[i]:
			ind = 0
			while ind < k and ind == ord(ans[-1]) - 65 or ind == ord(s[i + 1]) - 65:
				ind += 1
				ind %= k
			ans.append(alphs[ind % k])
			l += 1
		else:
			ans.append(s[i])
		i += 1
	print(l)
	print(''.join(ans))
main()


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
a = 'abcdefghijklmnopqrstuvwxyz'
a = a.upper()
(n, k) = I()
s = list(input() + 'aaa')
ans = 0
if k > 2:
	for i in range(1, n):
		if s[i] == s[i - 1]:
			for j in range(k):
				if a[j] != s[i - 1] and a[j] != s[i + 1]:
					ans += 1
					s[i] = a[j]
					break
			else:
				for j in range(k):
					if a[j] != s[i - 1]:
						ans += 1
						s[i] = a[j]
						break
else:
	x = 'AB' * (n // 2) + 'A' * (n % 2)
	y = 'BA' * (n // 2) + 'B' * (n % 2)
	a1 = 0
	a2 = 0
	for i in range(n):
		if s[i] != x[i]:
			a1 += 1
		if s[i] != y[i]:
			a2 += 1
	ans = min(a1, a2)
	s = [y, x][a1 < a2]
print(ans)
print(''.join(s[:n]))


import string
(n, k) = map(int, input().split())
r = list(input())
if k == 2:
	t = 'AB' * (n // 2) + 'A' * (n % 2)
	p = 'BA' * (n // 2) + 'B' * (n % 2)
	ct = 0
	cp = 0
	for i in range(n):
		if r[i] != t[i]:
			ct += 1
		if r[i] != p[i]:
			cp += 1
	if cp < ct:
		print(cp)
		print(''.join(p))
	else:
		print(ct)
		print(''.join(t))
else:
	ans = 0
	for i in range(1, n):
		c = list(string.ascii_uppercase)[:k]
		if r[i] == r[i - 1]:
			c.remove(r[i])
			if i + 1 < n and r[i + 1] in c:
				c.remove(r[i + 1])
			r[i] = c.pop()
			ans += 1
	print(ans)
	print(''.join(r))


import os, sys
from io import BytesIO, IOBase
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import *
from copy import *
import math
import string
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def charc(a, b):
	for i in range(3):
		if alpha[i] != a and alpha[i] != b:
			return alpha[i]

def charc2(a):
	if a == 'A':
		return 'B'
	else:
		return 'A'
(n, k) = map(int, input().split())
s = input()
res = []
for i in range(n):
	res.append(s[i])
alpha = string.ascii_uppercase[:k]
c = 0
if n == 1:
	print(0)
	print(s)
elif k == 2 or n == 2:
	if n % 2 == 0:
		res1 = 'AB' * (n // 2)
		res2 = 'BA' * (n // 2)
	else:
		res1 = 'AB' * (n // 2) + 'A'
		res2 = 'BA' * (n // 2) + 'B'
	c1 = 0
	c2 = 0
	for i in range(n):
		if s[i] != res1[i]:
			c1 += 1
		if s[i] != res2[i]:
			c2 += 1
	final = min(c1, c2)
	print(final)
	if final == c1:
		print(res1)
	else:
		print(res2)
else:
	for i in range(1, n - 1):
		temp = res[i]
		if res[i] != res[i - 1]:
			continue
		else:
			res[i] = charc(res[i + 1], res[i - 1])
			if res[i] == None:
				res[i] = temp
			else:
				c += 1
	if n > 2:
		if res[-2] == res[-1]:
			res[-1] = charc2(res[-2])
			c += 1
	print(c)
	print(''.join(res))


(n, k) = map(int, input().split())
s = input()
b = []
c = []
for j in s:
	b.append(j)
	c.append(j)
if n == 1:
	print(0)
	print(b[0])
elif n == 2:
	if b[0] == b[1]:
		print(1)
		print('AB')
	else:
		print(0)
		print(''.join(b))
elif k == 2:
	b[0] = 'A'
	j = 1
	s = 0
	while j < n:
		if b[j - 1] == b[j]:
			if b[j] == 'A':
				b[j] = 'B'
			else:
				b[j] = 'A'
			s += 1
		j += 1
	p = 0
	if c[0] == 'B':
		s += 1
	else:
		p += 1
	c[0] = 'B'
	j = 1
	while j < n:
		if c[j - 1] == c[j]:
			if c[j] == 'A':
				c[j] = 'B'
			else:
				c[j] = 'A'
			p += 1
		j += 1
	if p > s:
		print(s)
		print(''.join(b))
	else:
		print(p)
		print(''.join(c))
else:
	j = 0
	s = 0
	while j < n - 1:
		if j < n - 2 and b[j] == b[j + 1] and (b[j] == b[j + 2]):
			s += 1
			if ord(b[j]) - 64 == k:
				b[j + 1] = 'A'
			else:
				b[j + 1] = chr(ord(b[j]) + 1)
			j += 2
		elif j < n - 2 and b[j] == b[j + 1] and (b[j] != b[j + 2]):
			s += 1
			for p in range(65, 65 + k):
				if ord(b[j]) == p or ord(b[j + 2]) == p:
					pass
				else:
					b[j + 1] = chr(p)
					break
			j += 2
		elif j == n - 2 and b[j] == b[j + 1]:
			s += 1
			if ord(b[j]) - 64 == k:
				b[j + 1] = 'A'
			else:
				b[j + 1] = chr(ord(b[j]) + 1)
			j += 1
		elif b[j] != b[j + 1]:
			j += 1
	print(s)
	print(''.join(b))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
s = list(input().rstrip())
al = list('abcdefghijklmnopqrstuvwxyz'.upper())[:k]
al = set(al)
if k >= 3:
	cnt = 0
	for i in range(1, n - 1):
		if s[i - 1] == s[i] == s[i + 1]:
			s[i] = list(al - {s[i - 1]})[0]
			cnt += 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			if i < n - 1:
				s[i] = list(al - {s[i - 1]} - {s[i + 1]})[0]
			else:
				s[i] = list(al - {s[i - 1]})[0]
			cnt += 1
	print(cnt)
	print(''.join(s))
else:
	s1 = 'AB' * (n // 2) + 'A' * (n % 2)
	s2 = 'BA' * (n // 2) + 'B' * (n % 2)
	(cnt1, cnt2) = (0, 0)
	for i in range(n):
		if s[i] != s1[i]:
			cnt1 += 1
		if s[i] != s2[i]:
			cnt2 += 1
	if cnt1 < cnt2:
		print(cnt1)
		print(s1)
	else:
		print(cnt2)
		print(s2)


(n, k) = map(int, input().split())
s = input()
l = [chr(65 + i) for i in range(k)]
p = 0
if k == 2:
	q = 'AB' * (n // 2) + 'A' * (n % 2)
	w = 'BA' * (n // 2) + 'B' * (n % 2)
	o = 0
	for i in range(n):
		if s[i] != q[i]:
			p += 1
		if s[i] != w[i]:
			o += 1
	if p > o:
		print(o, '\n', w)
	else:
		print(p, '\n', q)
else:
	s = list(s + '0')
	for i in range(1, n):
		if s[i] == s[i - 1]:
			k = s[i]
			for j in l:
				if s[i - 1] != j and s[i + 1] != j:
					s[i] = j
					p += 1
					break
	print(p, '\n', ''.join(s[:-1]))


(n, k) = map(int, input().split())
s = list(input())
if k > 2:
	c = set((ord('A') + i for i in range(26)))
	r = 0
	for i in range(1, len(s)):
		if s[i - 1] == s[i]:
			r += 1
			if i + 1 < n:
				s[i] = 'A' if 'A' not in {s[i - 1], s[i + 1]} else 'B' if 'B' not in {s[i], s[i + 1]} else 'C'
			else:
				s[i] = 'A' if s[i - 1] != 'A' else 'B'
	print(r)
	print(''.join(s))
else:
	(x, y) = ('AB' * n, 'BA' * n)

	def check(x, y):
		return sum((x[i] != y[i] for i in range(n)))
	check_1 = check(x, s)
	check_2 = check(y, s)
	z = [x, y][check_1 > check_2]
	print(min(check_1, check_2))
	print(z[:n])


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	s = list(input())
	if n == 1:
		print(0)
		print(s[0])
		exit()
	if k == 2:
		(a, b) = ('A', 'B')
		(x, y) = (0, 0)
		for (i, item) in enumerate(s):
			if i % 2:
				if item == 'A':
					x += 1
				else:
					y += 1
			elif item == 'B':
				x += 1
			else:
				y += 1
		if x > y:
			print(y)
			print('BA' * (n // 2) + 'B' * (n % 2))
		else:
			print(x)
			print('AB' * (n // 2) + 'A' * (n % 2))
	else:
		(a, b, c) = ('A', 'B', 'C')
		ans = 0
		for i in range(1, n - 1):
			if s[i] == s[i - 1]:
				st = set([s[i - 1], s[i + 1]])
				if a not in st:
					s[i] = a
					ans += 1
				elif b not in st:
					s[i] = b
					ans += 1
				else:
					s[i] = c
					ans += 1
		if s[-1] == s[-2]:
			ans += 1
			if s[-2] == a:
				s[-1] = b
			else:
				s[-1] = a
		print(ans)
		print(*s, sep='')
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
alpha = 'QWERTYUIOPASDFGHJKLZXCVBNM'
index = {alpha[i]: i for i in range(26)}
(n, k) = value()
a = list(input())
i = 0
colors = sorted(alpha)[:k]
changes = 0
if k == 2:
	(ans1, ans2) = (0, 0)
	for i in range(n):
		if i % 2:
			if a[i] == 'B':
				ans1 += 1
			else:
				ans2 += 1
		elif a[i] == 'A':
			ans1 += 1
		else:
			ans2 += 1
	print(min(ans1, ans2))
	if ans1 < ans2:
		s1 = 'BA' * (n // 2)
		if n % 2:
			s1 += 'B'
		print(s1)
	else:
		s1 = 'AB' * (n // 2)
		if n % 2:
			s1 += 'A'
		print(s1)
else:
	while i < n:
		c = 0
		color = a[i]
		while i + 1 < n and color == a[i + 1]:
			i += 1
			c += 1
			if c % 2 == 1:
				a[i] = '-'
				changes += 1
		i += 1
	for i in range(len(a)):
		if a[i] == '-':
			if i == len(a) - 1:
				temp = a[i - 1]
			else:
				temp = (a[i - 1], a[i + 1])
			for j in range(k):
				if colors[j] not in temp:
					a[i] = colors[j]
					break
	print(changes)
	print(*a, sep='')


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

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

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = x
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
(n, k) = lint()
p = list(map(str, input().strip()))
s = p.copy()
ans = 0
if k == 2:
	tmp = ['A', 'B']
	cnt = 0
	for i in range(n):
		if s[i] != tmp[i % 2]:
			cnt += 1
	if cnt < n - cnt:
		c = (['A', 'B'] * (n // 2 + 1))[:n]
		print(cnt)
		print(''.join(c))
	else:
		c = (['A', 'B'] * (n // 2 + 1))[1:n + 1]
		print(n - cnt)
		print(''.join(c))
else:
	tmp = s[0]
	for i in range(1, n):
		if s[i] == tmp:
			for j in range(26):
				r = chr(65 + j)
				if r not in [s[i - 1], s[min(i + 1, n - 1)]]:
					s[i] = r
					tmp = r
					break
		else:
			tmp = s[i]
	for i in range(n):
		if s[i] != p[i]:
			ans += 1
	print(ans)
	print(''.join(s))


(n, k) = map(int, input().split())
s = list(input())
if n == 1:
	print(0)
	print(s[0])
	exit()
if k == 2:
	(a, b) = ('A', 'B')
	(x, y) = (0, 0)
	for i in range(n):
		item = s[i]
		if i % 2:
			if item == 'A':
				x += 1
			else:
				y += 1
		elif item == 'B':
			x += 1
		else:
			y += 1
	if x > y:
		print(y)
		print('BA' * (n // 2) + 'B' * (n % 2))
	else:
		print(x)
		print('AB' * (n // 2) + 'A' * (n % 2))
else:
	(a, b, c) = ('A', 'B', 'C')
	ans = 0
	for i in range(1, n - 1):
		if s[i] == s[i - 1]:
			(x, y) = (s[i - 1], s[i + 1])
			if a != x and a != y:
				s[i] = a
				ans += 1
			elif b != x and b != y:
				s[i] = b
				ans += 1
			else:
				s[i] = c
				ans += 1
	if s[-1] == s[-2]:
		ans += 1
		if s[-2] == a:
			s[-1] = b
		else:
			s[-1] = a
	print(ans)
	print(''.join(s))


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
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 = 1
for _ in range(t):
	solve()


import os
import sys
from io import BytesIO, IOBase
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
s = input()
if k == 2:
	s1 = 'AB' * (len(s) // 2)
	if len(s) % 2:
		s1 += 'A'
	s2 = 'BA' * (len(s) // 2)
	if len(s) % 2:
		s2 += 'B'
	ans1 = 0
	ans2 = 0
	for i in range(len(s)):
		if s1[i] != s[i]:
			ans1 += 1
		if s2[i] != s[i]:
			ans2 += 1
	if ans1 < ans2:
		print(ans1)
		print(s1)
	else:
		print(ans2)
		print(s2)
else:
	s1 = []
	ans = 0
	l = []
	i = 0
	while i < len(s):
		if i == len(s) - 1:
			l.append([1, len(s) - 1, len(s) - 1])
			break
		if s[i] == s[i + 1]:
			c = 1
			j = i
			while s[i] == s[i + 1]:
				c += 1
				i += 1
				if i == len(s) - 1:
					break
			l.append([c, j, i])
			i += 1
		else:
			l.append([1, i, i])
			i += 1
	for j in l:
		if j[0] == 1:
			s1.append(s[j[1]])
		else:
			a = 0
			for p in range(j[1], j[2] + 1):
				if a == 0:
					s1.append(s[p])
					a ^= 1
				else:
					for q in range(k):
						if chr(65 + q) != s[p]:
							s1.append(chr(65 + q))
							break
					ans += 1
					a ^= 1
			if j[0] % 2 == 0:
				if j[2] != len(s) - 1:
					if s1[j[2]] == s[j[2] + 1]:
						for p in range(k):
							if chr(65 + p) != s[j[2] + 1] and chr(65 + p) != s[j[2]]:
								s1[j[2]] = chr(65 + p)
								break
	print(ans)
	print(''.join(s1))


(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)


import math
(n, k) = map(int, input().split())
s = list(input())
alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
ltrs = alphabet[:k]
if k == 2:
	s1 = ('AB' * math.ceil(n / 2))[:n]
	s2 = ('BA' * math.ceil(n / 2))[:n]
	(diff1, diff2) = (0, 0)
	for i in range(n):
		if s1[i] != s[i]:
			diff1 += 1
		if s2[i] != s[i]:
			diff2 += 1
	if diff1 < diff2:
		print(diff1)
		print(s1)
	else:
		print(diff2)
		print(s2)
	exit()
c = 0
for i in range(1, n - 1):
	if s[i] == s[i - 1]:
		oneneed = 0
		c += 1
		for l in ltrs:
			if l != s[i - 1] and l != s[i + 1]:
				s[i] = l
				oneneed = 1
				break
		if oneneed == 0:
			for l in ltrs:
				if l != s[i - 1]:
					s[i] = l
					break
if n > 1:
	if s[-1] == s[-2]:
		for l in ltrs:
			if l != s[-2]:
				s[-1] = l
				c += 1
				break
print(c)
print(''.join(s))


(n, k) = map(int, input().split())
s = list(input())
if k <= 2:
	f = lambda t: sum((int(t[i] != s[i]) for i in range(n)))
	(x, y) = ('AB' * n, 'BA' * n)
	(res_x, res_y) = (f(x), f(y))
	if res_x > res_y:
		print(res_y)
		print(y[:n])
	else:
		print(res_x)
		print(x[:n])
	exit()
res = 0
for i in range(1, n):
	if s[i - 1] == s[i]:
		res += 1
		s[i] = list(set('ABC') - set(s[i:i + 2]))[0]
print(res)
print(''.join(s))


import os
import sys
from io import BytesIO, IOBase
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right
(n, k) = map(int, input().split())
s = list(input())
ans = 0
if k > 2:
	for (i, x) in enumerate(s):
		if i == 0:
			continue
		if s[i] == s[i - 1]:
			for j in range(k):
				if chr(j + 65) == s[i]:
					continue
				if i + 1 < n and s[i + 1] == chr(65 + j):
					continue
				s[i] = chr(65 + j)
				ans += 1
				break
	print(ans)
	print(''.join(s))
else:
	ans1 = 0
	ans2 = 0
	s1 = 'AB' * ((n + 1) // 2)
	s2 = 'BA' * ((n + 1) // 2)
	for (ind, i) in enumerate(s):
		if i != s1[ind]:
			ans1 += 1
	for (ind, i) in enumerate(s):
		if i != s2[ind]:
			ans2 += 1
	if ans1 <= ans2:
		print(ans1)
		c = ''.join(s1)
		print(c[:n])
	else:
		print(ans2)
		c = ''.join(s2)
		print(c[:n])


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate, permutations
from sys import stdout
R = lambda : map(int, input().split())
(n, k) = R()
s = input()
cnt = 0
if k == 2:
	(s1, s2) = (('AB' * ((n + 1) // 2))[:n], ('BA' * ((n + 1) // 2))[:n])
	cnt1 = cnt2 = 0
	for i in range(n):
		cnt1 += s[i] != s1[i]
		cnt2 += s[i] != s2[i]
	if cnt1 < cnt2:
		s = s1
		cnt = cnt1
	else:
		s = s2
		cnt = cnt2
else:
	s = list(s)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			for j in range(k):
				c = chr(ord('A') + j)
				if c != s[i - 1] and (i == n - 1 or c != s[i + 1]):
					s[i] = c
			cnt += 1
print(cnt)
print(''.join(s))


import bisect
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

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

def main():
	(n, k) = mii()
	s = li()
	a = ['A', 'B', 'C']
	cnt = 0
	if n == 1:
		print(0)
		print(''.join(s))
	elif n == 2:
		if s[0] != s[1]:
			print(0)
			print(''.join(s))
		else:
			print(1)
			if s[0] == 'A':
				print('AB')
			else:
				print(s[0] + 'A')
	elif k > 2:
		for i in range(1, n - 1):
			if s[i] == s[i - 1] and s[i] == s[i + 1]:
				cnt += 1
				s[i] = (set(a) - {s[i - 1], s[i + 1]}).pop()
		for i in range(1, n - 1):
			if s[i] == s[i - 1] or s[i] == s[i + 1]:
				cnt += 1
				s[i] = (set(a) - {s[i - 1], s[i + 1]}).pop()
		print(cnt)
		print(''.join(s))
	else:
		f = []
		ss = []
		for i in range(n):
			if i % 2 == 0:
				ss.append('B')
				f.append('A')
			else:
				f.append('B')
				ss.append('A')
		fc = 0
		sc = 0
		for i in range(n):
			if s[i] != f[i]:
				fc += 1
			else:
				sc += 1
		if fc < sc:
			print(cnt + fc)
			print(''.join(f))
		else:
			print(cnt + sc)
			print(''.join(ss))
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, k) = [int(x) for x in input().split()]
s = input()
if k == 2:
	str1 = 'AB' * n
	str2 = 'BA' * n
	diff1 = 0
	diff2 = 0
	for i in range(n):
		if s[i] != str1[i]:
			diff1 += 1
		else:
			diff2 += 1
	if diff1 < diff2:
		print(diff1)
		print(str1[:n])
	else:
		print(diff2)
		print(str2[:n])
else:
	l = [chr(i + ord('A')) for i in range(k)]
	s += '_'
	s = '_' + s
	s = list(s)
	resVal = 0
	for i in range(1, n + 1):
		if s[i] != s[i - 1]:
			continue
		resVal += 1
		possible_changes = [x for x in l if x != s[i - 1] and x != s[i + 1]]
		s[i] = possible_changes[0]
	del s[0]
	del s[-1]
	s = ''.join(s)
	print(resVal)
	print(s)


(n, k) = map(int, input().split())
s = input()
temp = []
for i in range(len(s)):
	temp.append(s[i])
ans = []
tans = []
for i in range(len(s)):
	ans.append(s[i])
	tans.append(s[i])
if k == 2:
	c1 = 0
	count = 0
	for i in range(len(ans)):
		if i % 2 == 0:
			if ans[i] == 'B':
				ans[i] = 'A'
				c1 += 1
		elif ans[i] == 'A':
			ans[i] = 'B'
			c1 += 1
	for i in range(len(tans)):
		if i % 2 == 0:
			if tans[i] == 'A':
				tans[i] = 'B'
				count += 1
		elif tans[i] == 'B':
			tans[i] = 'A'
			count += 1
	if count > c1:
		print(c1)
		print(''.join(map(str, ans)))
	else:
		print(count)
		print(''.join(map(str, tans)))
else:
	for i in range(1, len(ans)):
		if ans[i - 1] == ans[i]:
			if ans[i] == 'A':
				if i + 1 < len(ans):
					if ans[i + 1] == 'B':
						ans[i] = 'C'
					else:
						ans[i] = 'B'
				else:
					ans[i] = 'B'
			elif i + 1 < len(ans):
				if ans[i + 1] == 'A':
					if ans[i] == 'B':
						ans[i] = 'C'
					else:
						ans[i] = 'B'
				else:
					ans[i] = 'A'
			else:
				ans[i] = 'A'
	count = 0
	for i in range(len(temp)):
		if temp[i] != ans[i]:
			count += 1
	print(count)
	print(''.join(map(str, ans)))


(n, k) = map(int, input().split())
s = input()
l = []
ans = 0
if k == 2:
	s1 = []
	s2 = []
	for i in range(n):
		if i & 1:
			s1.append('A')
			s2.append('B')
		else:
			s2.append('A')
			s1.append('B')
	a1 = 0
	a2 = 0
	for i in range(n):
		if s[i] != s1[i]:
			a1 += 1
		if s[i] != s2[i]:
			a2 += 1
	if a1 > a2:
		print(a2)
		print(''.join(s2))
	else:
		print(a1)
		print(''.join(s1))
else:
	for i in range(n):
		if len(l) == 0:
			l.append(s[i])
		elif l[-1] == s[i]:
			if i != n - 1:
				a = l[-1]
				b = s[i + 1]
				if a == b:
					if a == 'A':
						l.append('B')
					else:
						l.append('A')
				elif a == 'A' and b != 'B':
					l.append('B')
				elif a == 'A' and b == 'B':
					l.append('C')
				elif a != 'B' and b == 'A':
					l.append('B')
				elif a == 'B' and b == 'A':
					l.append('C')
				else:
					l.append('A')
			elif l[-1] == 'A':
				l.append('B')
			else:
				l.append('A')
			ans += 1
		else:
			l.append(s[i])
	print(ans)
	print(''.join(l))


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)
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), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, k) = map(int, input().split())
s = list(input())
l = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')[:k]
ll = set(l)
if k >= 3:
	cnt = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cnt += 1
			if i + 1 < n:
				s[i] = list(ll - {s[i - 1]} - {s[i + 1]})[0]
			else:
				s[i] = list(ll - {s[i - 1]})[0]
	print(cnt)
	print(''.join(s))
else:
	x = ('AB' * n)[:n]
	y = ('BA' * n)[:n]
	(cnt1, cnt2) = (0, 0)
	for i in range(n):
		if x[i] != s[i]:
			cnt1 += 1
		if y[i] != s[i]:
			cnt2 += 1
	if cnt1 >= cnt2:
		print(cnt2)
		print(y)
	else:
		print(cnt1)
		print(x)