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:
//package acc;
import java.util.*;
import java.io.*;

   public  class ACC { 
//************Main*****************//
         
         public static void main(String[] args) throws IOException
			 {
             //   PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
              //  Scanner in=new Scanner (System.in);
               InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                InputReader in = new InputReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                int n=in.nextInt();
                int k=in.nextInt();
                String s=in.next();
                char arr[]=new char[s.length()+1];
                arr=s.toCharArray();;
                if(k==2){
                    
                    int ans1=0;
                    int ans2=0;
                    for(int i=0;i<s.length();i++){
                        if(i%2==0) {
                            if(arr[i]!='A')ans1++;
                            else ans2++;
                        }
                        else{
                            if(arr[i]!='B')ans1++;
                            else ans2++;
                        }
                    }
                  if(ans1<=ans2){
                      out.println(ans1);
                      for(int i=0;i<s.length();i++) {
                          if(i%2==0) out.print("A");
                          else out.print("B");
                      }
                  }
                  else{
                      out.println(ans2);
                      for(int i=0;i<s.length();i++) {
                          if(i%2==0) out.print("B");
                          else out.print("A");
                      }
                  }
                    
                }
                else{
                    int ans=0;
                    for(int i=1;i<s.length()-1;i++){
                        if(arr[i]==arr[i-1]){
                            ans++;
                            if(arr[i-1]!='A'&&arr[i+1]!='A') arr[i]='A';
                            if(arr[i-1]!='B'&&arr[i+1]!='B') arr[i]='B';
                            if(arr[i-1]!='C'&&arr[i+1]!='C') arr[i]='C';
                        }
                    }
                    if(s.length()>1)
                    if(arr[s.length()-1]==arr[s.length()-2]){
                        ans++;
                        if(arr[s.length()-1]!='A')arr[s.length()-1]='A';
                        else arr[s.length()-1]='B';
                    }
                    out.println(ans);
                    for(int i=0;i<s.length();i++) out.print(arr[i]);
                }
                out.close();
         }
         
   }
    class Pair implements Comparable<Pair>{
    int x,y;
    public  Pair(int X,int Y){
        super();
x=X;
y=Y;
}
    @Override
      public int compareTo(Pair p){
       return Integer.compare(x, p.x);
}
  }
class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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