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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class E {
	static int n,k;
	static int [] a;
	static PrintWriter pw;
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		pw=new PrintWriter(System.out,true);
		
		n=sc.nextInt();
		k=sc.nextInt();
		a=new int [n];
		char [] c=sc.next().toCharArray();
		for(int i=0;i<n;i++)
			a[i]=c[i]-'A';
		mem=new int [n+1][30];
		for(int i=0;i<n+1;i++)
			Arrays.fill(mem[i], -1);
		pw.println(dp(0, 29));
		dp2(0, 29);
		pw.println();
		pw.flush();
		pw.close();
	}
	static int [][]mem;
	static int INF=(int)(1e6);
	
	public static void dp2(int i,int last){
		if(i==n)
			return;
		if(a[i]!=last && dp(i+1,a[i])==mem[i][last]){
			pw.print((char)(a[i]+'A'));
			dp2(i+1, a[i]);
		}else
		for(int j=0;j<Math.min(k, 3);j++)
			if(j!=last && 1+dp(i+1,j)==mem[i][last]){
				pw.print((char)(j+'A'));
				dp2(i+1, j);
				break;
			}
	}
	
	
	public static int dp(int i,int last){
		if(i==n)
			return 0;
		if(mem[i][last]!=-1)
			return mem[i][last];
		int ans=INF;
		if(a[i]!=last)
			ans=Math.min(ans, dp(i+1, a[i]));
		for(int j=0;j<Math.min(k, 3);j++){
			if(j!=last)
				ans=Math.min(ans, 1+dp(i+1, j));
		}
		return mem[i][last]=ans;
	}
	
	
	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;
	      }

	   }
}