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.*;
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;

public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;

        tk = new StringTokenizer(in.readLine());
        int n = parseInt(tk.nextToken()),k = parseInt(tk.nextToken());
        
        char [] c = in.readLine().toCharArray();
        
        if(k==2) {
          char [] tmp1={'A','B'},tmp2={'B','A'};
          int cc=0;
          
          char [] c1 = new char[n];
          char [] c2 = new char[n];
          for(int i=0; i<n; i++) 
              c1[i] = c2[i] = c[i];
          
          int cnt1=0,cnt2=0;
          for(int i=0; i<n; i++) {
              if(tmp1[cc]!=c1[i]) {
                  cnt1++;
                  c1[i] = tmp1[cc];
              }
              
              if(tmp2[cc]!=c2[i]) {
                  cnt2++;
                  c2[i] = tmp2[cc];
              }
              
              cc ^= 1;
          }
          
          if(cnt1 <= cnt2) {
              System.out.println(cnt1);
              System.out.println(valueOf(c1));
          } else {
              System.out.println(cnt2);
              System.out.println(valueOf(c2));
          }
          
          return;
        }
        
        
        
        int ans = 0;
        
        for(int i=1; i<n; i++) {
            if(c[i]==c[i-1]) {
                if(i<n-1 && c[i]==c[i+1]) c[i] = getNextChar(c[i],k);
                else {
                    c[i] = getNextChar(c[i],k);
                    
                    if(i<n-1 && c[i]==c[i+1])
                        c[i] = getNextChar(c[i],k);
                }
                ans++;
            }
        }
        
        System.out.println(ans);
        System.out.println(valueOf(c));
    }
    
    static char getNextChar(char c,int k) {
        if(c-'A' < k-1)
            return ++c;
        return 'A';
    }
    
}