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 C {
	public void solve() throws IOException {
		int n = nextInt();
		int k = nextInt();
		String str = nextToken();
		StringBuilder ret = new StringBuilder();
		int count = 0;
		if( k == 2 ){
			int count_a = 0;
			int count_b = 0;
			for(int i = 0; i < str.length(); i++){
				if( i%2 == 0 && str.charAt(i) == 'A' ){
					count_a++;
				} else if( i%2 == 1 && str.charAt(i) == 'B' ){
					count_b++;
				}
			}
			int a = (n%2 == 1) ? n/2 + 1 : n/2;
			int b = n/2;
			int key = (a-count_a) + (b-count_b);
			if( key < n-key ){
				for(int i = 0; i < n; i++){
					if( i%2 == 0 ){
						ret.append("A");
					} else {
						ret.append("B");
					}
				}
				writer.println(key);
				writer.println(ret);
			} else {
				for(int i = 0; i < n; i++){
					if( i%2 == 0 ){
						ret.append("B");
					} else {
						ret.append("A");
					}
				}
				writer.println(n-key);
				writer.println(ret);
			}
			return;
		}
		ret.append(str.charAt(0));
		for(int i = 1; i < str.length(); i++){
			char x = str.charAt(i);
			char y = ret.charAt(i-1);
			if( x != y ){
				ret.append(x);
			} else {
				count++;
				char z = (i+1 < str.length()) ? str.charAt(i+1) : 0;
				for(int j = 0; j < k; j++){
					if( j != (y-'A') && j != (z-'A') ){
						ret.append((char)('A'+j));
						break;
					}
				}
			}
		}
		writer.println(count);
		writer.println(ret);		
	}

	public static void main(String[] args) throws IOException {
		new C().run();
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;

	public void run() throws IOException {
		try {
			reader = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			writer = new PrintWriter(System.out);
			solve();
			reader.close();
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	public String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

}