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.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

import javax.xml.bind.ValidationEvent;


public class DynamicProgrammingPractice {
	public static void main(String[] args) {
		//tetrahedron(System.in);
		//poloThePenguinAndMatrix(System.in);
		//System.out.println(anotherProblemOnStrings(System.in));
		//theLeastRoundWay(System.in);								// TODO
		colorStripe(System.in);								// TODO
		//colorStripeTest();
	}

	public static void colorStripeTest() {
		int n = 500000;
		int k = 26;
		char[] c = new char[n];
		Random rand = new Random(0);
		for (int i = 0; i < c.length; i++) {
			c[i] = (char) ('A' + rand.nextInt(k));
		}
		long time = System.currentTimeMillis();
		colorStripe(n, k, c);
		time = System.currentTimeMillis() - time;
		System.out.println(time);
	}

	public static void colorStripe(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		char[] a = scan.nextLine().toCharArray();
		
		colorStripe(n, k, a);
	}
	
	public static void colorStripe(int n, int k, char[] a) {

		int[] dp = new int[k];
		byte[][] back = new byte[n][k];
//		for (int i = 0; i < dp.length; i++) {
//			Arrays.fill(dp[i], Integer.MAX_VALUE);
//		}
		for (int i = 0; i < k; i++) {
			dp[i] = i == (a[0] - 'A') ? 0 : 1;
		}
		for (int i = 1; i < n; i++) {
			int[] newDp = new int[k];
			ArrayList<int[]> list = new ArrayList<>();
			for (int j = 0; j < k; j++) {
				list.add(new int[]{dp[j], j});
			}
			Collections.sort(list, new Array1Comp());
			int[] l1 = list.get(0);
			int[] l2 = list.get(1);
			
			for (int j = 0; j < k; j++) {
				int min = Integer.MAX_VALUE;
				if (l1[1] != j) {
					min = l1[0];
					back[i][j] = (byte) l1[1];
				} else {
					min = l2[0];
					back[i][j] = (byte) l2[1];
				}
				min += j == (a[i] - 'A') ? 0 : 1;
				newDp[j] = min;
			}
			dp = newDp;
		}
		
		int min = Integer.MAX_VALUE;
		int minIdx = 0;
		for (int i = 0; i < k; i++) {
			if (dp[i] < min) {
				min = dp[i];
				minIdx = i;
			}
		}
		
		char[] ret = new char[n];
		int current = minIdx;
		for (int i = n-1; i >= 0; i--) {
			ret[i] = (char) (current + 'A');
			current = back[i][current];
		}
		System.out.println(min);
		System.out.println(new String(ret));
	}

	public static class Array1Comp implements Comparator<int[]> {
		@Override
		public int compare(int[] o1, int[] o2) {
			if (o1[0] < o2[0]) {
				return -1;
			} else if (o1[0] > o2[0]) {
				return 1;
			} else {
				return 0;
			}
		}
	}
	
	public static class Array2Comp implements Comparator<int[]> {
		@Override
		public int compare(int[] o1, int[] o2) {
			return Integer.compare(o1[1], o2[1]);
		}
	}

	public static void theLeastRoundWay(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int[][] a = new int[n][n];
		for (int i = 0; i < n; i++) {
			a[i] = scan.nextIntArray(n);
		}
		int[][] backtrack = new int[n][n];
		int[][][] dp = new int[n][2][2];
		int[][][] nextDp = new int[n][2][2];
		for (int i = 0; i < n; i++) {
			nextDp = new int[n][2][2];
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < 2; k++) {
					int[] rem = {0, 0};
					int x = a[i][j];
					while (x > 0 && x % 2 == 0) {
						rem[0]++;
						x /= 2;
					}
					while (x > 0 && x % 5 == 0) {
						rem[1]++;
						x /= 5;
					}
					if (i == 0 && j == 0) {
						for (int m = 0; m < 2; m++) {
							nextDp[j][k][m] = rem[m];
						}
					} else if (i == 0) {
						for (int m = 0; m < 2; m++) {
							nextDp[j][k][m] = (nextDp[j-1][k][m] + rem[m]);
							backtrack[i][j] = 1;
						}
					} else if (j == 0) {
						for (int m = 0; m < 2; m++) {
							nextDp[j][k][m] = (dp[j][k][m] + rem[m]);
							backtrack[i][j] = 2;
						}
					} else {
						ArrayList<int[]> list = new ArrayList<>();
						list.add(new int[]{dp[j][0][0], dp[j][0][1], 2});
						list.add(new int[]{dp[j][1][0], dp[j][1][1], 2});
						list.add(new int[]{nextDp[j-1][0][0], nextDp[j-1][0][1], 1});
						list.add(new int[]{nextDp[j-1][1][0], nextDp[j-1][1][1], 1});
						if (k == 0) {
							Collections.sort(list, new Array1Comp());
						} else {
							Collections.sort(list, new Array2Comp());
						}
						for (int m = 0; m < 2; m++) {
							nextDp[j][k][m] = (list.get(0)[m] + rem[m]);
							backtrack[i][j] = list.get(0)[2];
						}
					}
				}
			}
			dp = nextDp;
		}
		int min = Integer.MAX_VALUE;
		ArrayList<Character> path = new ArrayList<>();
		int x = n-1;
		int y = n-1;
		while (x >= 0 && y >= 0) {
			if (backtrack[y][x] == 0) {
				break;
			} else if (backtrack[y][x] == 1) {
				path.add('R');
				x--;
			} else {
				path.add('D');
				y--;
			}
		}
		Collections.reverse(path);
		StringBuilder sb = new StringBuilder();
		for (char c: path) {
			sb.append(c);
		}
		for (int k = 0; k < 2; k++) {
			for (int m = 0; m < 2; m++) {
				min = Math.min(dp[n-1][k][m], min);
			}
		}
		System.out.println(min);
		System.out.println(sb);
	}
	
	public static void test() {
		Random rand = new Random(0);
		int max = 1000;
		int numTests = 1000;
		for (int t = 0; t < numTests; t++) {
			int k = rand.nextInt(max);
			char[] s = new char[rand.nextInt(max)];
			for (int i = 0; i < s.length; i++) {
				s[i] = (char) (rand.nextInt(2) + '0');
			}
			anotherProblemOnStrings(k, s);
		}
	}

	public static long anotherProblemOnStrings(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int k = scan.nextInt();
		char[] s = scan.nextLine().toCharArray();
		return anotherProblemOnStrings(k, s);
	}
	
	private static long anotherProblemOnStrings(int k, char[] s) {

		int start = 0;
		ArrayList<Integer> ones = new ArrayList<>();
		for (int i = 0; i < s.length; i++) {
			if (s[i] == '1') {
				ones.add(i);
			}
		}
		if (k == 0) {
			ArrayList<Integer> numZ = new ArrayList<>();
			int len = 0;
			if (s[0] == '0') {
				len++;
			}
			for (int i = 1; i < s.length; i++) {
				if (s[i] == '0' && s[i-1] == s[i]) {
					len++;
				} else if (s[i] == '0') {
					len = 1;
				} else {
					numZ.add(len);
					len = 0;
				}
			}
			numZ.add(len);
			long total = 0;
			for (int i = 0; i < numZ.size(); i++) {
				total += (long)numZ.get(i) * (numZ.get(i)+1)/2;
			}
			return total;
		} 
		if (ones.isEmpty()) {
			return 0;
		}
		int end = 0;
		long total = 0;
		for (int i = 0; i < ones.size()-k+1; i++) {
			start = ones.get(i);
			end = ones.get(i + k-1);
			int leftZ = 0;
			int rightZ = 0;
			start--;
			while (start >= 0 && start <= s.length && s[start] == '0') {
				leftZ++;
				start--;
			}
			end++;
			while (end >= 0 && end < s.length && s[end] == '0') {
				rightZ++;
				end++;
			}
			total += (long)(leftZ+1) * (rightZ +1);
		}
		return total;
	}

	public static void poloThePenguinAndMatrix(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int d = scan.nextInt();
		int[][] a = new int[n][m];
		for (int i = 0; i < a.length; i++) {
			a[i] = scan.nextIntArray(m);
		}
		
		boolean valid = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (Math.abs(a[0][0] - a[i][j]) % d != 0) {
					valid = false;
				}
			}
		}
		
		if (!valid) {
			System.out.println(-1);
			return;
		}
		
		int min = Integer.MAX_VALUE;
		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				min = Math.min(min, a[i][j]);
				max = Math.max(max, a[i][j]);
			}
		}
		
		int best = Integer.MAX_VALUE;
		for (int i0 = min; i0 <= max; i0+=d) {
			int total = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					total += Math.abs(a[i][j] - i0)/d;
				}
			}
			best = Math.min(best, total);
		}
		
		System.out.println(best);
	}

	public static final int mod = 1000000007;
	public static void tetrahedron(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int[] dp = new int[4];
		dp[3] = 1;
		for (int i = 1; i <= n; i++) {
			int[] nextDp = new int[4];
			for (int j = 0; j < nextDp.length; j++) {
				for (int k = 0; k < nextDp.length; k++) {
					if (k != j) {
						nextDp[j] = (nextDp[j] + dp[k]) % mod;
					}
				}
			}
			dp = nextDp;
		}
		System.out.println(dp[3]);
	}

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner(InputStream in) {
			this.br = new BufferedReader(new InputStreamReader(in));
		}

		public void close() {
			try {
				this.br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					String s = br.readLine();
					if (s != null) {
						st = new StringTokenizer(s);
					} else {
						return null;
					}
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = this.nextLong();
			}
			return a;
		}

		int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = this.nextInt();
			}
			return a;
		}

		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;
		}
	}
}