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 com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here
        StringBuilder sb = new StringBuilder();
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int k=s.nextInt();
        char[] a=s.next().toCharArray();long [][] dp=new long[n][k];
        if(k==2){
        for(int i=0;i<n;i++){
            for(int j=65;j<65+k;j++){
                dp[i][j-65]=Long.MAX_VALUE;
            }
        }int[] []  val=new int[n][k];
        for(int i=0;i<n;i++){
            for(int cur=65;cur<65+k;cur++){
                for(int j=65;j<65+k;j++){
                    if(i>0){
                        if(cur==a[i]){    if(j==cur) continue;
                            if(dp[i-1][j-65]<dp[i][cur-65]) val[i][cur-65]=j;
                            dp[i][cur-65]=Math.min(dp[i][cur-65],dp[i-1][j-65]);
                        }else{
                            if(j==cur) continue;
                            if(dp[i-1][j-65]+1<dp[i][cur-65]) val[i][cur-65]=j;
                            dp[i][cur-65]=Math.min(dp[i][cur-65],dp[i-1][j-65]+1);
                        }
                    }else{
                        if(cur==a[i]) dp[i][cur-65]=0;
                        else dp[i][cur-65]=1;
                    }
                }


            }
        }long ans=Long.MAX_VALUE;char fc='A';
        for(int i=65;i<65+k;i++){
            if(dp[n-1][i-65]<ans) fc=(char)i;
            ans=Math.min(ans,dp[n-1][i-65]);
        }char[] fans=new char[n];fans[n-1]=fc;int i=n-1;
        while(i>0){
            fans[i-1]=(char)val[i][fc-65];
            fc=fans[i-1];i--;
        }
        System.out.println(ans);
        for(int j=0;j<n;j++){
            sb.append(fans[j]);
        }
        System.out.println(sb.toString());}
        else{
            long ans=0;
            for(int i=1;i<n;i++){
                if(a[i]==a[i-1]){
                    char z=(char)(a[i]+1);
                    if(z==65+k)
                        z=65;
                    if((i+1<n&&z==a[i+1])) z++;
                    if(z==65+k) z=65;
                    ans++;
                    a[i]=z;
                }}
            System.out.println(ans);
            for(int i=0;i<n;i++){

                sb.append(a[i]);
            }
            System.out.println(sb.toString());

        }
    }}