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.LinkedList;
import java.util.List;
import java.util.Scanner;


public class Main {
	public static void main(String [] args){
		Scanner sc = new Scanner (System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		String s= sc.nextLine();
		s= sc.nextLine();
		//System.out.println(s);
		//long a=System.currentTimeMillis();
		TaskC c= new TaskC();
		c.solve(n,k,s);
		//System.out.println(String.format("\n%d\n", System.currentTimeMillis()-a));
	}

}
class TaskC{
	int maxm=500005;
	int maxn=26;
	int [] dp_pre = new int[maxn];
	int [] dp_cur = new int[maxn];
	int [][] track=new int[maxm][maxn];
	String letters="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	//if not same dp[i pos-1][X]  = dp[i pos][C]
	//if same, dp[i pos-1][x] = dp[i pos][x+1%k]
	char [] colors= null;//new char[26];


	public void solve(int n,int k,String s){
		colors=letters.toCharArray(); 
		char [] ori = s.toCharArray();
		//init
		for(int i=0;i<k;i++){
			dp_pre[i]=1;
			track[0][i]=i;
		}
		dp_pre[ ori[0]-'A' ]=0;
		track[0][ ori[0]-'A' ] = ori[0]-'A';
		//track[0]
		//xx
		int plus;
		int [] min_array={0,0};
		List<String> sb=new LinkedList<String>();
		for(int i=1;i<n;i++){
			for(int init=0;init<k;init++){
				dp_cur[init]=maxm;
			}
			int cur_min_j=-1;
			int cur_sec_min_j=-1;
			int cur_min=maxm;
			int cur_sec_min=maxm;
			
			if (dp_pre[0]>dp_pre[1]){
				cur_min_j=1;
				cur_sec_min_j=0;
				cur_min=dp_pre[1];
				cur_sec_min=dp_pre[0];
			}else{
				cur_min_j=0;
				cur_sec_min_j=1;
				cur_min=dp_pre[0];
				cur_sec_min=dp_pre[1];
			}
			
			for(int init=2;init<k;init++){
				if(dp_pre[init]<cur_min){
					cur_min=dp_pre[init];
					cur_sec_min_j=cur_min_j;
					cur_min_j=init;
				}else{
					//dp_pre[init]> min
					if(dp_pre[init]< cur_sec_min){
						cur_sec_min_j=init;
						cur_sec_min=dp_pre[init];
					}
					//dp_pre[init]>min and sec_min;
				}
			}
			min_array[0]=cur_min_j;
			min_array[1]=cur_sec_min_j;
			
			//only min and sec_min to update the other.
			//only update  cur +-1;
			// j-> other 26 except j.
			for(int min_j : min_array){
				int cur = ori[i]-'A';
				//int left_cur=0;
				//left_cur=Math.max(0, cur-1);
				//int right_cur=k;
				//right_cur=Math.min(k-1,cur+1);
				for( int mm=0;mm<k;mm++){
					if(mm!=min_j){
						plus=0;
						if(mm!=cur){
							plus=1;
						}
						
						if(dp_pre[min_j]+plus < dp_cur[mm]){
							dp_cur[mm]=dp_pre[min_j]+plus;
							track[i][mm]=min_j;
						}
	
					}
				}
			}
			
			for(int init=0;init<k;init++){
				dp_pre[init]=dp_cur[init];
			}
		}
		int min_res=maxm;
		int min_j=-1;
		for(int j=0;j<k;j++){
			if(dp_pre[j]<min_res){
				min_res=dp_pre[j];
				min_j=j;
			}
		
		}
		System.out.println(min_res);
		//System.out.print(String.format("%c", min_j+'A'));
		//char [] res= new char[n];
		StringBuilder xb= new StringBuilder();
		for(int i=n-1;i>=0;i--){
			xb.append((char) (min_j+'A'));
			//res[i]=
			//sb.add(String.format("%c", min_j+'A'));
			min_j=track[i][min_j];
		}
		

		System.out.println(xb.reverse().toString());
		
		
		
		
		
		
		
		
		
	}
}