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.DataInputStream;
import java.io.InputStream;
import java.io.PrintWriter;

public class Main {

    
    public static void main(String[] args) throws Exception {
        Parserdoubt23 s = new Parserdoubt23(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = s.nextInt();
        int k = s.nextInt();
        
        char cccc[] = s.nextString().toCharArray();
        int c[] = new int[cccc.length];
        for (int i = 0; i < c.length; i++) {
            c[i] = cccc[i] - 'A';
        }
        
        
        if(k == 2){
            int one[] = new int[c.length];
            int two[] = new int[c.length];
            for (int i = 0; i < c.length; i++) {
                if(i%2 == 0){
                    one[i] = 0;
                    two[i] = 1;
                }
                else{
                    one[i] = 1;
                    two[i] = 0;
                }
            }
            
            int ans1 = 0;
            int ans2 = 0;
            for (int i = 0; i < c.length; i++) {
                if(one[i] != c[i]) ans1++;
                if(two[i] != c[i]) ans2++;
                
            }
            
            if(ans1 < ans2){
                out.println(ans1);
                for (int i = 0; i < c.length; i++) {
                    out.print((char)(one[i]+'A'));
                }
                out.println();
            }
            else{
                out.println(ans2);
                for (int i = 0; i < c.length; i++) {
                    out.print((char)(two[i]+'A'));
                }
                out.println();
            }
            out.close();
            return ;
            
        }
        
        
        
        
        int count = 0;
        
        int repainted = 0;
        
        char rez[] = new char[c.length];
        for (int i = 0; i < c.length; i++) {
            int left = i;
            int right = i + 1;
            while(right < c.length && c[left] == c[right]) right++;
            
            int before = -1;
            if(left-1 >= 0) before = c[left-1];
            
            int after = -1;
            if(right < c.length) after = c[right];
            
            int len = right - left;
            
            int chosen = -1;
            for (int j = 0; j < k; j++) {
                if(after != j && c[left] != j){
                    chosen = j;
                    break;
                }
            }
            
//          System.out.println(i+" "+len +" ::: "+chosen);
            for (int j = 0; j < len; j++) {
                if(j%2 == 0)
                    rez[left+j] = (char)(c[left]+'A');
                else{
                    rez[left+j] = (char)(chosen+'A');
                    repainted++;
                }
            }
            i = right - 1;
        }
        out.println(repainted);
        
        for (int i = 0; i < rez.length; i++) {
            out.print(rez[i]);
        }
        out.println();
        out.close();
    }

}




class Parserdoubt23
{
   final private int BUFFER_SIZE = 1 << 18;
 
   private DataInputStream din;
   private byte[] buffer;
   private int bufferPointer, bytesRead;
 
   public Parserdoubt23(InputStream in)
   {
      din = new DataInputStream(in);
      buffer = new byte[BUFFER_SIZE];
      bufferPointer = bytesRead = 0;
   }
   public String nextString() throws Exception
   {
       StringBuffer sb=new StringBuffer("");
       byte c = read();
       while (c <= ' ') c = read();
       do
       {
           sb.append((char)c);
           c=read();
       }while(c>' ');
       return sb.toString();
   }
   public char nextChar() throws Exception
   {
       byte c=read();
       while(c<=' ') c= read();
       return (char)c;
   }
   public int nextInt() throws Exception
   {
      int ret = 0;
      byte c = read();
      while (c <= ' ') c = read();
      boolean neg = c == '-';
      if (neg) c = read();
      do
      {
          ret = ret * 10 + c - '0';
         c = read();
      } while (c > ' ');
      if (neg) return -ret;
      return ret;
   }
   public long nextLong() throws Exception
   {
      long ret = 0;
      byte c = read();
      while (c <= ' ') c = read();
      boolean neg = c == '-';
      if (neg) c = read();
      do
      {
          ret = ret * 10 + c - '0';
         c = read();
      } while (c > ' ');
      if (neg) return -ret;
      return ret;
   }
   private void fillBuffer() throws Exception
   {
      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
      if (bytesRead == -1) buffer[0] = -1;
   }
 
   private byte read() throws Exception
   {
      if (bufferPointer == bytesRead) fillBuffer();
      return buffer[bufferPointer++];
   }
}