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 P219C {

  private static void solve() {
    int n = nextInt();
    int k = nextInt();

    String s = next();
    char[] origChars = s.toCharArray();

    if (k == 2) {
      StringBuilder sb = new StringBuilder();
      StringBuilder sb2 = new StringBuilder();

      int s1 = 0;
      for (int i = 0; i < n; i++) {
        sb.append((char)('A' + s1));
        sb2.append((char)('A' + (s1 + 1) % 2));
        s1 = (s1 + 1) % 2;
      }

      int ans1 = 0;
      int ans2 = 0;

      String st = sb.toString();
      String st2 = sb2.toString();

      for (int i = 0; i < n; i++) {
        if (st.charAt(i) != s.charAt(i)) {
          ans1++;
        }

        if (st2.charAt(i) != s.charAt(i)) {
          ans2++;
        }
      }

      if (ans1 < ans2) {
        System.out.println(ans1);
        System.out.println(st);
      } else {
        System.out.println(ans2);
        System.out.println(st2);
      }


    } else {
      int origAns = find(origChars, n, k);
      System.out.println(origAns);
      System.out.println(new String(origChars));
    }
  }

  private static int find(char[] c, int n, int k) {
    int local = 0;
    char last = c[0];
    for (int i = 1; i < n; i++) {
      if (last == c[i]) {
        if (i + 1 < n) {
          if (c[i] == c[i + 1]) {
            c[i] = (char) (((c[i] - 'A' + 1) % k) + 'A');
          } else {
            if (k == 2) {
              c[i] = c[i + 1];
            } else {
              if (c[i + 1] > c[i]) {
                if (c[i + 1] - c[i] > 1) {
                  c[i] = (char)(c[i] + 1);
                } else {
                  c[i] = (char)(((c[i + 1] - 'A' + 1) % k) + 'A');
                }
              } else {
                if (c[i] - c[i + 1] > 1) {
                  c[i] = (char)(c[i + 1] + 1);
                } else {
                  c[i] = (char)(((c[i] - 'A' + 1) % k) + 'A');
                }
              }
            }
          }
        } else {
          c[i] = (char) (((c[i] - 'A' + 1) % k) + 'A');
        }
        local++;
      }
      last = c[i];
    }

    return local;
  }

  private static void run() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);

    solve();

    out.close();
  }

  private static StringTokenizer st;
  private static BufferedReader br;
  private static PrintWriter out;

  private static String next() {
    while (st == null || !st.hasMoreElements()) {
      String s;
      try {
        s = br.readLine();
      } catch (IOException e) {
        return null;
      }
      st = new StringTokenizer(s);
    }
    return st.nextToken();
  }

  private static int nextInt() {
    return Integer.parseInt(next());
  }

  private static long nextLong() {
    return Long.parseLong(next());
  }

  public static void main(String[] args) {
    run();
  }
}