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

Solution:
import java.util.StringTokenizer;
import java.util.Collections;
import java.util.Collection;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.Vector;
import java.util.Hashtable;
import java.util.Iterator;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.FileReader;

import java.math.BigInteger;

public class Main extends Exception
{

	static PrintWriter writer;
	static StringTokenizer sz;
	static BufferedReader reader;

	public static void main(String[] args)
	throws Exception
	{
		declare();

		readLine();
		n = readInt();
		int i=0,k = readInt();

		str = readString().toCharArray();
		colors = new char[26];

		for (char ch='A';ch <= 'Z';++ch)
			colors[i++] = ch;

		if (k == 2)
		{
			int c1,c2;

			c1 = count('A', 'B');
			c2 = count('B', 'A');

			if (c1 <= c2)
			{
				writer.println(c1);
				print('A', 'B');
			}
			else
			{
				writer.println(c2);
				print('B', 'A');
			}

		}
		else
		{
			int ans,freqChar;
			freqChar = 1;
			ans = 0;

			for (int c=1;c < n;++c)
			{
				if (str[c - 1] == str[c])
				{
					++freqChar;

					if (freqChar == 3)
					{
						str[c - 1] = search(str[c], str[c]);
						freqChar = 1;
						++ans;
					}

				}
				else
				{
					if (freqChar == 2)
					{
						str[c - 1] = search(str[c], str[c - 1]);
						++ans;
					}
					freqChar = 1;
				}
			}

			if (freqChar == 2)
			{
				++ans;
				str[n - 1] = search(str[n - 1], str[n - 1]);
			}

			writer.println(ans);
			for (char ch:str)
				writer.print(ch);

		}


		close();
	}

	static char str[],colors[];
	static int n;

	private static int count(char f, char s)
	{
		int count = 0;

		for (int i=0;i < n;++i)
			if (i % 2 == 0)
				count += str[i] != f ? 1: 0;
			else
				count += str[i] != s ? 1: 0;

		return count;
	}

	private static void print(char f, char s)
	{
		for (int i=0;i < n;++i)
			if (i % 2 == 0)
				writer.print(f);
			else
				writer.print(s);
	}

	private static char search(char f, char s)
	{
		for (char ch='A';ch <= 'Z';++ch)
			if (ch != f && ch != s)
				return ch;

		return 'a';
	}

	private static class Pair implements Comparable<Pair>
	{
		int first,second;

		public Pair(int f, int s)
		{
			first = f;
			second = s;
		}

		public Pair(Pair p)
		{
			first = p.first;
			second = p.second;
		}

		@Override
		public int compareTo(Main.Pair p1)
		{

			if (first == p1.first)
				return  second - p1.second;
			return first - p1.first;

		}

		@Override
		public String toString()
		{
			return first + " " + second + "\n";
		}
	}

	private static String readString()
	throws IOException
	{
		if (sz.hasMoreTokens())
			return sz.nextToken();
		return reader.readLine();
	}

	private static void readLine()
	throws IOException
	{
		sz = new StringTokenizer(reader.readLine());
	}

	private static int readInt()
	throws IOException
	{
		if (sz.hasMoreTokens())
			return Integer.parseInt(sz.nextToken());
		return Integer.parseInt(reader.readLine());
	}

	private static long readLong()
	throws IOException
	{
		if (sz.hasMoreTokens())
			return Long.parseLong(sz.nextToken());
		return Long.parseLong(reader.readLine());
	}

	private static void declare()
	{
		writer = new PrintWriter(System.out);
		reader = new BufferedReader(
			new InputStreamReader(System.in));
		sz = new StringTokenizer("");
	}

	private static void declareFile()
	throws IOException
	{
		writer = new PrintWriter("output.txt");
		reader = new BufferedReader(
			new FileReader("input.txt"));
		sz = new StringTokenizer("");
	}

	private static void close()
	throws IOException
	{
		reader.close();
		writer.flush();
		writer.close();
	}
}