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.util.*;
import java.io.*;

public class C
{
   public static void main(String[] args)
   {
      new C(new FastScanner());
   }

   int[] convert(char[] cs)
   {
      int[] res = new int[cs.length];
      int ptr = 0;
      for (char c : cs)
         res[ptr++] = (int)(c-'A');
      return res;
   }

   public C(FastScanner in)
   {
      int N = in.nextInt();
      int K = in.nextInt();
      int[] vs = convert(in.next().toCharArray());
      
      int[][] prev = new int[K][N+1];
      int[][] dp = new int[K][N+1];
      
      int oo = 987654321;
      for (int[] dd : dp)
         Arrays.fill(dd, oo);
      
      Comparator<int[]> cmp = new Comparator<int[]>(){
         public int compare(int[] a, int[] b)
         {
            return a[0]-b[0];
         }
      };

      for (int j=0; j<K; j++)
         dp[j][0] = 0;
      
      int[][] tmp = new int[K][2]; 
      for (int i=0; i<N; i++)
      {
         for (int j=0; j<K; j++)
         {
            tmp[j][0] = dp[j][i];
            tmp[j][1] = j;
         }
         Arrays.sort(tmp, cmp);

         for (int k=0; k<K; k++)
         {
            int cost = (k!=vs[i]?1:0);
         
            int pv = tmp[0][1];
            if (tmp[0][1] == k)
            {
               cost += tmp[1][0];
               pv = tmp[1][1];
            }
            else
            {
               cost += tmp[0][0];
            }

            if (cost < dp[k][i+1])
            {
               dp[k][i+1] = cost;
               prev[k][i+1] = pv;
            }
         }
      }

      StringBuilder sb = new StringBuilder();
      
      int bestStart = 0;
      for (int j=1; j<K; j++)
         if (dp[j][N] < dp[bestStart][N])
            bestStart = j;
     
      PrintWriter out = new PrintWriter(System.out);
      out.println(dp[bestStart][N]);
      int jj = bestStart;
      for (int i=N; i>0; i--)
      {
         sb.append((char)('A'+jj));
         jj = prev[jj][i];
      }
      sb.reverse();
      out.println(sb);
      out.close();
   }
}

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

   public FastScanner()
   {
      stream = System.in;
   }

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

   boolean isSpaceChar(int c)
   {
      return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
   }
   
   boolean isEndline(int c)
   {
      return c=='\n'||c=='\r'||c==-1;
   }

   int nextInt()
   {
      return Integer.parseInt(next());
   }
   
   long nextLong()
   {
      return Long.parseLong(next());
   }

   double nextDouble()
   {
      return Double.parseDouble(next());
   }

   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();
   }
   
   String nextLine(){
      int c = read();
      while (isEndline(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isEndline(c));
      return res.toString();
   }
}