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.StringTokenizer;


public class ColorStripe {
	static IR in = new IR(System.in);
	static char[] c;
	static StringBuilder sb = new StringBuilder();
	static int N,K;
	static int moves =0;
	

	static char get(char c){
		for(int i=0;i<K;i++) if((char)(('A'+i))!=c) return (char)(('A'+i));
		return 'a';
	}
	static char getdiffthan(char c1,char c3){
		for(int i=0;i<K;i++) if(((char)(('A'+i))!=c1)&&((char)('A'+i)!=c3)) return (char)(('A'+i));
		return 'a';
	}
	static void change(int j){
		if(j==N-1){ c[j] = get(c[j]); moves++;}
		else{
			c[j] = getdiffthan(c[j],c[j+1]); moves++;

		}

	}
	public static void main(String[]args)throws Throwable{
		N =in.j(); K = in.j(); c = in.next().toCharArray(); 
		if(K==2){
			StringBuilder sb2 = new StringBuilder();
			char c1 = c[0]; char c2 = c1=='A'?'B':'A';
			boolean a = true;
			for(int i=0;i<N;i++){
				if(a){
					sb.append(c1); a = false;
				}
				else{
					a = true; sb.append(c2);
				}
			}
			 a = true;
			 int m2 = 0;
			for(int i=0;i<N;i++){
				if(a){
					sb2.append(c2); a = false;
				}
				else{
					a = true; sb2.append(c1);
				}
			}
			for(int i=0;i<N;i++) {
				if(c[i]!=sb.charAt(i))moves++;
				if(c[i]!=sb2.charAt(i))m2++;
			}
			
			if(moves<m2){System.out.println(moves);
			System.out.println(sb);}
			else{
				System.out.println(m2); System.out.println(sb2);
			}
			return;
		}
		for(int i=0;i<N-1;i++){
			if(c[i]==c[i+1]) change(i+1);
			sb.append(c[i]);
			//System.out.println(sb);
		}
		sb.append(c[N-1]);
		System.out.println(moves);
		System.out.println(sb);
	}







	static	class IR {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public IR(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int j() {
			return Integer.parseInt(next());
		}
		public long ll(){
			return Long.parseLong(next());
		}


	}
}