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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main1 {
	
	static int n,k;
	static char[] a;
	static int[][] memo;
	static StringBuilder dpPrint;
	
	static int dp(int i,int prev)
	{
		if(i==n)return 0;
		if(memo[i][prev]!=-1)return memo[i][prev];
		int ans = Integer.MAX_VALUE;
		if(a[i]-'A'!=prev)ans = dp(i+1,a[i]-'A');
		for(int kk = 0;kk<k;kk++)
			if(kk!=prev && kk!=a[i]-'A')
				ans = Math.min(ans,1+dp(i+1,kk));
		return memo[i][prev] = ans;
	}
	
	static void print2(int prev)
	{
		int i = 1;
		while(i<n)
		{
			int curAns = dp(i,prev);
			if(a[i]-'A'!=prev && curAns==dp(i+1,a[i]-'A'))
			{
				dpPrint.append(a[i]);
				prev = a[i]-'A';
				++i;
			}
			else
			{
				for(int kk = 0;kk<k;kk++)
				{
					if(kk!=prev && kk!=a[i]-'A' && (1+dp(i+1,kk))==curAns)
					{
						dpPrint.append((char)(kk+'A'));
						++i;
						prev = kk;
						break;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws Throwable {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt() ; k = sc.nextInt();
		a = sc.nextLine().toCharArray();
		if(k>3)
		{
			int i = 0 , j = 0 , z , ans = 0;
			while(i<n)
			{
				while(++j<n && a[j]==a[i]);
				ans += (j-i)>>1;
				char c = 'A';
				String s = ""+a[i]+(i-1>0?a[i-1]:a[i])+(j<n?a[j]:a[i]);
				for(int h = 0;h<k;h++)
				{
					if(!s.contains(((char)(h+'A'))+""))
					{
						c = (char) (h+'A');
						break;
					}
				}
				for(z = i+1;z<j;z+=2)a[z]=c;
				i=j;
			}
			System.out.println(ans);
			StringBuilder sb = new StringBuilder();
			for(char c : a)
				sb.append(c);
			System.out.println(sb);
		}
		else
		{
			memo = new int[n][k];
			for(int i = 0; i < memo.length;i++)
				Arrays.fill(memo[i], -1);
			for(int i = n-1;i>=0;i-=100)
				for(int j = 0;j<k;j++)
					dp(i,j);
			int ans = Integer.MAX_VALUE;
			for(int i = 0; i < k;i++)
				ans = Math.min(ans,(i==a[0]-'A'?0:1)+ dp(1,i));
			dpPrint = new StringBuilder();
			for(int i = 0; i < k;i++)
			{
				if(ans==(i==a[0]-'A'?0:1)+ dp(1,i))
				{
					dpPrint.append((char)(i+'A'));
					print2(i);
					break;
				}
			}
			System.out.println(ans);
			System.out.println(dpPrint);
		}
	}
	
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}
}