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.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.*;
 
public class ColorStripe {
	
	private static class MyScanner {
	    BufferedReader br;
	    StringTokenizer st;

	    public MyScanner() {
	       br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    String next() {
	        while (st == null || !st.hasMoreElements()) {
	            try {
	                st = new StringTokenizer(br.readLine());
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	        }
	        return st.nextToken();
	    }

	    int nextInt() {
	        return Integer.parseInt(next());
	    }

	    long nextLong() {
	        return Long.parseLong(next());
	    }

	    double nextDouble() {
	        return Double.parseDouble(next());
	    }

	    String nextLine(){
	        String str = "";
		  try {
		     str = br.readLine();
		  } catch (IOException e) {
		     e.printStackTrace();
		  }
		  return str;
	    }

	 }
	

	
	public static void solution(int n, int k, String st)
			
	{
		int count = 0;
		
		if(k==2)
		{
			StringBuilder f1 = new StringBuilder("");
			StringBuilder f2 = new StringBuilder("");
			
			for(int i = 0; i<n; i++)
			{
				if(i%2==0)
					f1.append('A');
				else
					f1.append('B');
			}
			
			for(int i = 0; i<n; i++)
			{
				if(i%2==0)
					f2.append('B');
				else
					f2.append('A');
			}
			
			int c1 = 0;
			
			for(int i = 0; i<n; i++)
			{
				if(st.charAt(i)!=f1.charAt(i))
					c1++;
			}
			
            int c2 = 0;
			
			for(int i = 0; i<n; i++)
			{
				if(st.charAt(i)!=f2.charAt(i))
					c2++;
			}
			
			
			if(c1<=c2)
			{
				out.println(c1);
				out.println(f1);
			}
			
			else
			{
				out.println(c2);
				out.println(f2);
			}
			
		 return;		
				
		}
		
		
		StringBuilder sb = new StringBuilder("");
		sb.append(st.charAt(0));
		
		for(int i = 1; i<n; i++)
		{
			if(st.charAt(i)==sb.charAt(i-1))
			{
				
				if(i<n-1 && st.charAt(i+1)!=st.charAt(i))
				{
						if(st.charAt(i)!='A')
							{
								if(st.charAt(i+1)!='A')
								  sb.append('A');
								else
								{
									if(st.charAt(i)!='B')
										 sb.append('B');
									else
										
										sb.append('C');
										  
								}
							}
						
						else
						{
							if(st.charAt(i+1)!='B')
							  sb.append('B');
							else
							    {
								   if(k>2)
								     sb.append('C');
								   else
									  sb.append('B');
								}
							
						}
						
					}
				
				else
				{	
				   if(st.charAt(i)!='A')
				      sb.append('A');
				   else
					 sb.append('B'); }
				
				count++;
			}
			
			else
				sb.append(st.charAt(i));
			
		}
		
		out.println(count);
		out.println(sb.toString());
	}
        
private static PrintWriter out = new PrintWriter(System.out);

public static void main (String[] args)
{
	MyScanner s =  new MyScanner();
 
	int n = s.nextInt();
	int k = s.nextInt();
    String st = s.nextLine();
    	
    solution(n,k,st);
    
    
    out.flush();
    out.close();
    
}
}