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.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.ObjectInputStream.GetField;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

public class Q2 {
	static long MOD = 1000000007;
	static boolean b[];
	static ArrayList<Integer>[] amp;
	static int sum[],dist[];
	static long ans = 0;
	static int p = 0;
	static FasterScanner sc = new FasterScanner();
	static Queue<Integer> q = new LinkedList<>();
	static ArrayList<String>[] arr;
	static ArrayList<Integer> parent = new ArrayList<>();
	static BufferedWriter log;
	static HashMap<Long,Long> hm;
	static Pair prr[];
	public static void main(String[] args) throws IOException {
		log = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = sc.nextInt(), k = sc.nextInt();
		String str = sc.nextLine();
		if(n==1){
			System.out.println("0");
			System.out.println(str);
		}
		else if(n==2){
			if(str.charAt(0)==str.charAt(1)){
				System.out.println("1");
				if(str.charAt(0)=='A'){
					System.out.println("AB");
				}
				else System.out.println("BA");
			}
			else{
				System.out.println("0");
				System.out.println(str);
			}
		}
		else if(k>=3){
			char ch[] = str.toCharArray();
			int cnt = 0;
			for(int i = 1;i<n-1;i++){
				if(ch[i]!=ch[i-1]){
					continue;
				}
				else{
					ch[i] = give(ch[i-1],ch[i+1]);
					cnt++;
				}
			}
			if(ch[n-1]==ch[n-1-1]){
				ch[n-1] = give(ch[n-1],'A');
				cnt++;
			}
			String ans1 = new String(ch);
			System.out.println(cnt);
			System.out.println(ans1);
			
		}
		else{
			char ch[] = str.toCharArray();
			int cnt1 = 0;
			for(int i = 1;i<n;i++){
				if(ch[i]!=ch[i-1]){
					continue;
				}
				else{
					if(ch[i-1]=='A') ch[i] = 'B';
					else ch[i] = 'A';
					cnt1++;
				}
			}
			String ans1 = new String(ch);
			if(cnt1>n/2){
				System.out.println(n-cnt1);
				StringBuilder sb = new StringBuilder();
				for(int i = 0;i<n;i++){
					if(ans1.charAt(i)=='A') sb.append('B');
					else sb.append('A');
				}
				System.out.println(sb.toString());
			}
			else{
				System.out.println(cnt1);
				System.out.println(ans1);
			}/*
			ch = str.toCharArray();
			int cnt2 = 0;
			for(int i = n-2;i>=0;i--){
				if(ch[i]!=ch[i+1]){
					continue;
				}
				else{
					if(ch[i+1]=='A') ch[i] = 'B';
					else ch[i] = 'A';
					cnt2++;
				}
			}
			String ans2 = new String(ch);
			if(cnt1<cnt2) {
				System.out.println(cnt1);
				System.out.println(ans1);
			}
			else {
				System.out.println(cnt2);
				System.out.println(ans2);
			}
		}*/
		}
		log.close();
	}
	public static char give(char c1,char c2){
		if(c1!='A' && c2!='A') return 'A';
		if(c1!='B' && c2!='B') return 'B';
		return 'C';
	}
	static class Graph{
		int vertex;
		long weight;
	}
	public static void buildTree(int n){
		int arr[] = sc.nextIntArray(n);
		for(int i = 0;i<n;i++){
			int x = arr[i]-1;
			amp[i+1].add(x);
			amp[x].add(i+1);
		}
	}
	public static void bfs(int x,long arr[]){
		
		b[x] = true;
		q.add(x);
		while(!q.isEmpty()){
			int y = q.poll();
			for(int i = 0;i<amp[y].size();i++) {
				if(!b[amp[y].get(i)]){
					q.add(amp[y].get(i));
					b[amp[y].get(i)] = true;
				}
			}
		}
	}
		
	public static void buildGraph(int n){
		
		for(int i =0;i<n;i++){
			int x = sc.nextInt(), y = sc.nextInt();
			amp[--x].add(--y);
			amp[y].add(x);
			prr[i] = new Pair(x,y);
		}
	}
		
	public static void dfs(int x){
		b[x] = true;
		for(int i =0 ;i<amp[x].size();i++){
			if(!b[amp[x].get(i)]){
				dfs(amp[x].get(i));
			}
		}
		
	}
	static class Pair implements Comparable<Pair> {
		long u;
		long v;
		public Pair(){
			
		}
		public Pair(long u, long v) {
			this.u = u;
			this.v = v;
		}
		
		public int hashCode() {
			int hu = (int) (u ^ (u >>> 32));
			int hv = (int) (v ^ (v >>> 32));
			return 31*hu + hv;
		}

		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return (u == other.u && v == other.v);
		}

		public int compareTo(Pair other) {
			return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : (Long.compare(v, other.v));
		}
		
		public String toString() {
			return "[u=" + u + ", v=" + v + "]";
		}
	}
	static class SegmentTree{
		int st[][];
		SegmentTree(char arr[], int n){
			int size = 4*n+1;
			st = new int[size][3];
			build(arr,0,n-1,0);
		}
		int[] build(char arr[], int ss, int se, int si){
			if(ss==se){
				st[si][0] = 0;
				if(arr[ss]=='(')
				st[si][1] = 1;
				else st[si][2] = 1;
				return st[si];
			}
			int mid = (ss+se)/2;
			int amp[] = build(arr,ss,mid,si*2+1);
			int bmp[] = build(arr,mid+1,se,si*2+2);
			int t = Math.min(amp[1], bmp[2]);
			st[si][0] = amp[0]+bmp[0]+2*t;
			st[si][1] = amp[1]+bmp[1]-t;
			st[si][2] = amp[2]+bmp[2]-t;
			return st[si];
		}
		int[] getXor(int qs, int qe, int ss, int se, int si){
			if(qe<ss || qs>se){
				return null;
			}
			if(qs<=ss && qe>=se) return st[si];
			int mid = (ss+se)/2;
			int amp[]= getXor(qs,qe,ss,mid,2*si+1);
			int bmp[] = getXor(qs,qe, mid+1, se, 2*si+2);
			if(amp==null) return bmp;
			else if(bmp == null) return amp;
			int[] a=new int[3];
            int t=Math.min(amp[1],bmp[2]);
            a[0]=amp[0]+bmp[0]+2*t;
            a[1]=amp[1]+bmp[1]-t;
            a[2]=amp[2]+bmp[2]-t;
            return a;
		}
		void print(){
			for(int i = 0;i<st.length;i++){
				for(int j = 0;j<3;j++)
				System.out.print(st[i][j]+" ");
				System.out.println("----------------------");
			}
		}
	}
	static int convert(int x){
		int cnt = 0;
		String str = Integer.toBinaryString(x);
		//System.out.println(str);
		for(int i = 0;i<str.length();i++){
			if(str.charAt(i)=='1'){
				cnt++;
			}
		}
		int ans = (int) Math.pow(3, 6-cnt);
		return ans;
	}
	static class Node2{
		Node2 left = null;
		Node2 right = null;
		Node2 parent = null;
		int data;
	}
	static class BinarySearchTree{
		Node2 root = null;
		int height = 0;
		int max = 0;
		int cnt = 1;
		ArrayList<Integer> parent = new ArrayList<>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		public void insert(int x){
			Node2 n = new Node2();
			n.data = x;
			if(root==null){
				root = n;
			}
			else{
				Node2 temp = root,temp2 = null;
				while(temp!=null){
					temp2 = temp;
					if(x>temp.data) temp = temp.right;
					else temp = temp.left;
				}
				if(x>temp2.data) temp2.right = n;
				else temp2.left = n;
				n.parent = temp2;
				parent.add(temp2.data);
			}
		}
		public Node2 getSomething(int x, int y, Node2 n){
			if(n.data==x || n.data==y) return n;
			else if(n.data>x && n.data<y) return n;
			else if(n.data<x && n.data<y) return getSomething(x,y,n.right);
			else return getSomething(x,y,n.left);
		}
		public Node2 search(int x,Node2 n){
			if(x==n.data){
				max = Math.max(max, n.data);
				return n;
			}
			if(x>n.data){
				max = Math.max(max, n.data);
				return search(x,n.right);
			}
			else{
				max = Math.max(max, n.data);
				return search(x,n.left);
			}
		}
		public int getHeight(Node2 n){
			if(n==null) return 0;
			height = 1+ Math.max(getHeight(n.left), getHeight(n.right));
			return height;
		}
	}
	static long findDiff(long[] arr, long[] brr, int m){
		int i = 0, j = 0;
		long fa = 1000000000000L;
		while(i<m && j<m){
			long x = arr[i]-brr[j];
			if(x>=0){
				if(x<fa) fa = x;
				j++;
			}
			else{
				if((-x)<fa) fa = -x;
				i++;
			}
		}
		return fa;
	}
	public static long max(long x, long y, long z){
		if(x>=y && x>=z) return x;
		if(y>=x && y>=z) return y;
		return z;
	}
	
	public static void seive(long n){
		b = new boolean[(int) (n+1)];
		Arrays.fill(b, true);
		for(int i = 2;i<=n;i++){
			if(b[i]){
				for(int p = 2*i;p<=n;p++){
					b[p] = false;
				}
			}
		}
	}
	static long modInverse(long a, long mOD2){
	            return  power(a, mOD2-2, mOD2);
	}
	static long power(long x, long y, long m)
	{
	    if (y == 0)
	        return 1;
	    long p = power(x, y/2, m) % m;
	    p = (p * p) % m;
	 
	    return (y%2 == 0)? p : (x * p) % m;
	}
	static long power2(long x,BigInteger y,long m){
		long ans = 1;
		BigInteger two = new BigInteger("2");
		while(y.compareTo(BigInteger.ZERO)>0){
			if(y.getLowestSetBit()==y.bitCount()){
				x = (x*x)%MOD;
				y = y.divide(two);
			}
			else{
				ans = (ans*x)%MOD;
				y = y.subtract(BigInteger.ONE);
			}
		}
		return ans;
	}
	static BigInteger power2(BigInteger x, BigInteger y, BigInteger m){
		BigInteger ans = new BigInteger("1");
		BigInteger one  = new BigInteger("1");
		BigInteger two  = new BigInteger("2");
		BigInteger zero  = new BigInteger("0");
		while(y.compareTo(zero)>0){
			//System.out.println(y);
			if(y.mod(two).equals(one)){
				ans = ans.multiply(x).mod(m);
				y = y.subtract(one);
			}
			else{
				x = x.multiply(x).mod(m);
				y = y.divide(two);
			}
		}
		return ans;
	}
	static BigInteger power(BigInteger x, BigInteger y, BigInteger m)
	{
	    if (y.equals(0))
	        return (new BigInteger("1"));
	    BigInteger p = power(x, y.divide(new BigInteger("2")), m).mod(m);
	    p = (p.multiply(p)).mod(m);
	 
	    return (y.mod(new BigInteger("2")).equals(0))? p : (p.multiply(x)).mod(m);
	}
	static long d,x,y;
	public static void extendedEuclidian(long a, long b){
		if(b == 0) {
	        d = a;
	        x = 1;
	        y = 0;
	    }
	    else {
	        extendedEuclidian(b, a%b);
	        int temp = (int) x;
	        x = y;
	        y = temp - (a/b)*y;
	    }
	}
	
	public static long gcd(long n, long m){
		if(m!=0) return gcd(m,n%m);
		else return n;
	}
	
	
	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
 
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = System.in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
 
		public String nextString() {
			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 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 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 int[] nextIntArray(int n) {
	        return nextIntArray(n, 0);
	    }
	    
	    public int[] nextIntArray(int n, int off) {
	    	int[] arr = new int[n + off];
	    	for (int i = 0; i < n; i++) {
	    		arr[i + off] = nextInt();
	    	}
	    	return arr;
	    }
	    
	    public long[] nextLongArray(int n) {
	    	return nextLongArray(n, 0);
	    }
        
		public long[] nextLongArray(int n, int off) {
		    long[] arr = new long[n + off];
		    for (int i = 0; i < n; i++) {
		        arr[i + off] = nextLong();
		    }
		    return arr;
		}
 
	    private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}
}