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;
void debug() {
  fflush(stdin);
  printf("Press any key to continue");
  getc(stdin);
  fflush(stdin);
}
int n, k;
string s;
int main() {
  scanf("%d%d", &n, &k);
  cin >> s;
  int ans = 0;
  if (k != 2) {
    int l = 0, r;
    while (l < n) {
      r = l + 1;
      while (r < n && s[r] == s[l]) r++;
      for (int i = l + 1; i <= r - 1; i += 2) {
        char cl = '.', cr = '.';
        if (i > 0) cl = s[i - 1];
        if (i + 1 < n) cr = s[i + 1];
        for (int j = 0; j < k; j++) {
          char tmp = j + 'A';
          if (tmp != cl && tmp != cr) {
            ans++;
            s[i] = tmp;
            break;
          }
        }
      }
      l = r;
    }
  } else {
    string s1 = s;
    string s2 = s;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
      if (i % 2 == 1 && s1[i] == 'A') {
        s1[i] = 'B';
        ans1++;
      } else if (i % 2 == 0 && s1[i] == 'B') {
        s1[i] = 'A';
        ans1++;
      }
      if (i % 2 == 1 && s2[i] == 'B') {
        s2[i] = 'A';
        ans2++;
      } else if (i % 2 == 0 && s2[i] == 'A') {
        s2[i] = 'B';
        ans2++;
      }
    }
    if (ans1 < ans2) {
      ans = ans1;
      s = s1;
    } else {
      ans = ans2;
      s = s2;
    }
  }
  printf("%d\n", ans);
  cout << s << endl;
  return 0;
}