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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
  int t, i, j, k, n, m;
  cin >> n >> k;
  string s;
  cin >> s;
  int ans = 0;
  if (k == 2) {
    int cn = 0;
    int cr = 0;
    string an;
    for (i = 0; i < s.size(); i++) {
      if (cr != s[i] - 'A') cn++;
      an += char('A' + cr);
      cr = 1 - cr;
    }
    ans = cn;
    cr = 1;
    cn = 0;
    string an2;
    for (i = 0; i < s.size(); i++) {
      if (cr != s[i] - 'A') cn++;
      an2 += char('A' + cr);
      cr = 1 - cr;
    }
    if (ans < cn) {
      cout << ans << endl;
      cout << an << endl;
    } else {
      cout << cn << endl;
      cout << an2 << endl;
    }
    return 0;
  } else {
    int pre = 1;
    string an;
    for (i = 1; i < s.size(); i++) {
      if (s[i] == s[i - 1])
        pre++;
      else {
        ans += pre / 2;
        char x = s[i - 1];
        char x2;
        if (pre % 2 == 1) {
          if (x == 'A')
            x2 = 'B';
          else
            x2 = 'A';
          for (j = 0; j < pre; j++) {
            if (j % 2 == 0)
              an += x;
            else
              an += x2;
          }
        } else {
          char c = s[i];
          for (char r = 'A'; r <= 'Z'; r++) {
            if (r != c && r != x) {
              x2 = r;
              break;
            }
          }
          for (j = 0; j < pre; j++) {
            if (j % 2 == 0)
              an += x;
            else
              an += x2;
          }
        }
        pre = 1;
      }
    }
    ans += pre / 2;
    char x = s[i - 1];
    char x2;
    if (x == 'A')
      x2 = 'B';
    else
      x2 = 'A';
    if (pre % 2 == 1) {
      for (j = 0; j < pre; j++) {
        if (j % 2 == 0)
          an += x;
        else
          an += x2;
      }
    } else {
      for (j = 0; j < pre; j++) {
        if (j % 2 == 0)
          an += x;
        else
          an += x2;
      }
    }
    cout << ans << endl;
    cout << an << endl;
  }
  return 0;
}