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.List;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Main {
	private int k;
	private void solve() throws IOException {
		int n = nextInt();
		k = nextInt();
		
		char arr[] = nextToken().toCharArray();
		int c[] = new int[n];
		for (int i = 0; i < n; ++i)
			c[i] = (short)(arr[i] - 'A');

		if (k == 2) {
			int cnt1 = 0;
			int cnt2 = 0;
			for (int i = 0; i < n; ++i)
				if (i % 2 == 0) {
					if (c[i] == 1) cnt1++;
					else cnt2++;
				}
				else if (c[i] == 0) cnt1++;
				else cnt2++;
			
			if (cnt1 < cnt2) {
				pw.println(cnt1);
				for (int i = 0 ; i < n; ++i)
					if (i % 2 == 0) pw.print("A");
					else pw.print("B");
			} else {
				pw.println(cnt2);
				for (int i = 0 ; i < n; ++i)
					if (i % 2 == 0) pw.print("B");
					else pw.print("A");
			}
			return;
		}
		
		List<Integer> l = new ArrayList<>();
		List<Integer> r = new ArrayList<>();
		int i = 0;
		while(i < n - 1) {
			if (c[i + 1] == c[i]) {
				l.add(i);
				while (i < n - 1 && c[i + 1] == c[i]) ++i;
				r.add(i);
			}
			++i;
		}
		
		ListIterator<Integer> li = l.listIterator();
		ListIterator<Integer> ri = r.listIterator();
		
		int cnt = 0;
		while (li.hasNext()) {
			int f = li.next();
			int s = ri.next();
			if ((s- f + 1) % 2 == 1) {
				int cl = another(c[f]);
				for (i = f + 1; i < s; i += 2) { 
					c[i] = cl;
					cnt++;
				}
			} else {
				int cl = another(c[f], (((s + 1) < n) ? c[s + 1] : c[f]));
				for (i = f + 1; i <= s; i += 2) { 
					c[i] = cl;
					cnt++;
				}
			}
		}
		
		pw.println(cnt);
		for ( i = 0 ; i < n; ++i)
			pw.print((char) (c[i] + 'A'));
	}
	
	private int another(int ... ls) {
		Arrays.sort(ls);
		for (int i = 0; i < k; ++i) {
			int ind = Arrays.binarySearch(ls, i);
			if (ind < 0)  return i;
		}
		throw new IllegalArgumentException();
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

	public void run() {
		try {
			pw = new PrintWriter(System.out);
			br = new BufferedReader(new InputStreamReader(System.in));
			solve();
			pw.close();
			br.close();
		} catch (IOException e) {
			System.err.println("IO Error");
		}
	}

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

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

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

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

		return tokenizer.nextToken();
	}
	
	private BufferedReader br;
	private StringTokenizer tokenizer;
	private PrintWriter pw;
}