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.*;
import java.io.*;

public class Main{

	static int mod=(int)1e9+7;
	
	public static void main(String[] args) throws IOException {
		PrintWriter out=new PrintWriter(System.out);
		Reader in=new Reader(System.in);	
		int ts=1;
//		ts=in.nextInt();
		outer: while(ts-->0) {
			
			int n=in.nextInt();
			int k=in.nextInt();
			
			char s[]=in.next().toCharArray();
			if(k==2) {
				char c='A';
				int opA=minEx(s,'A'), opB=minEx(s,'B');
				if(opA>opB) c='B';
				for(int i=0; i<n; ++i) {
					s[i]=c;
					c=(char)(1-c+'A'+'A');
				}
				if(s[0]=='A') out.println(opA);
				else out.println(opB);
				out.println(String.valueOf(s));
			} else {
				int count=0;
				for(int i=1; i<n-1; ++i) {
					if(s[i-1]==s[i] && s[i]==s[i+1]) {
						correct(s,i,k);
						count++;
					}
				}
				for(int i=0; i<n-1; ++i) {
					if(s[i]==s[i+1]) { 
						correct2(s,i,k);
						count++;
					}
				}
				out.println(count);
				out.println(String.valueOf(s));
			}
			
			
		}
		out.close();	
	}
	
	static void correct(char s[], int i, int k) {
		for(char c='A'; c<k+'A'; ++c) {
			if(c!=s[i-1]) {
				s[i]=c;
				break;
			}
		}
	}
	
	static void correct2(char s[], int i, int k) {
		for(char c='A'; c<k+'A'; ++c) {
			if(i==0 && c!=s[i+1]) {
				s[i]=c;
				break;
			}
			else if(i>0 && c!=s[i-1] && c!=s[i+1]) {
				s[i]=c;
				break;
			}
		}
	}
	
	static int minEx(char s[], char c) {
		int count=0;
		for(int i=0; i<s.length; i++) {
			if(s[i]!=c) count++;
			c=(char)(1-c+'A'+'A');
		}
		return count;
	}
	
	static void sort(int [] a) {
		List<Integer> l=new ArrayList<>();
		for(int i: a) l.add(i);
		Collections.sort(l);
		for(int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
	static class Reader{
		BufferedReader br;
		StringTokenizer to;
		Reader(InputStream stream){
			br=new BufferedReader(new InputStreamReader(stream));
			to=new StringTokenizer("");
		}
		String next() {
			while(!to.hasMoreTokens()) {
				try {
					to=new StringTokenizer(br.readLine());	
				}catch(IOException e) {}
				
			}
			return to.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int [] readArray(int n) {
			int a[]=new int[n];
			for(int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
	}	
	
}