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.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main1 {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		String s = sc.next();
		
		if(K == 2){
			//special case, just brute-force it
			StringBuilder a = new StringBuilder();
			StringBuilder b = new StringBuilder();
			int totalA = 0;
			int totalB = 0;
			for(int i = 0; i<N; i++){
				if(i%2 == 0){
					a.append('A');
					b.append('B');
					if(s.charAt(i) == 'A') totalB++;
					else totalA++;
				}
				else{
					a.append('B');
					b.append('A');
					if(s.charAt(i) == 'A') totalA++;
					else totalB++;
				}
			}
			if(totalA > totalB){
				System.out.println(totalB);
				System.out.println(b);
			}
			else{
				System.out.println(totalA);
				System.out.println(a);
			}
		}
		else{
			StringBuilder sb = new StringBuilder();
			int total = 0;
			sb.append(s.charAt(0));
			for(int i = 1; i<N; i++){
				char a = sb.charAt(i-1);
				char b = s.charAt(i);
				char c = '.';
				if(i+1 < N) c = s.charAt(i+1);
				
				if(a == b){
					total++;
					if(a != 'A' && c != 'A') b = 'A';
					else if(a != 'B' && c != 'B') b = 'B';
					else b = 'C';
				}
				
				sb.append(b);
			}
			System.out.println(total);
			System.out.println(sb);
		}
	}
}

class FastScanner {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public FastScanner(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String next() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public String nextLine() {
		int c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isLineEndChar(c));
		return res.toString();
	}

	public double nextDouble() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		double res = 0;
		while (!isSpaceChar(c) && c != '.') {
			if (c == 'e' || c == 'E')
				return res * Math.pow(10, nextInt());
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		}
		if (c == '.') {
			c = read();
			double m = 1;
			while (!isSpaceChar(c)) {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				m /= 10;
				res += (c - '0') * m;
				c = read();
			}
		}
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public boolean isLineEndChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == '\n' || c == '\r' || c == -1;
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}