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>
const long long mod = (1e9 + 7);
using namespace std;
template <typename T>
ostream& operator<<(ostream& o, vector<T> a) {
  size_t n = a.size();
  for (size_t i = 0; i < n; i++) {
    o << a[i];
  }
  o << "\n";
  return o;
}
template <typename T>
void display(T a[], int n) {
  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}
template <typename T>
ostream& operator<<(ostream& o, map<int, T> m) {
  size_t n = m.size();
  auto it = m.begin();
  for (; it != m.end(); it++) {
    o << (*it).first << " " << (*it).second << "\n";
  }
  return o;
}
int solve() {
  int n, k;
  cin >> n >> k;
  vector<char> a(n);
  int ans = 0;
  for (long long i = 0; i < n; i++) cin >> a[i];
  if (n != 2) {
    if (k != 2) {
      for (int i = 1; i < n;) {
        while (i < n && a[i] != a[i - 1]) {
          i++;
        }
        int j = i;
        while (j < n && a[j] == a[j - 1]) j++;
        if ((j - i + 1) % 2) {
          if (a[i] == 'A')
            for (int k = i; k < j; k += 2) {
              a[k] = 'B';
            }
          else
            for (int k = i; k < j; k += 2) {
              a[k] = 'A';
            }
        } else {
          if (a[i - 1] != 'A' && a[j] != 'A') {
            for (int k = i; k < j; k += 2) {
              a[k] = 'A';
            }
          } else if (a[i - 1] != 'B' && a[j] != 'B')
            for (int k = i; k < j; k += 2) {
              a[k] = 'B';
            }
          else
            for (int k = i; k < j; k += 2) {
              a[k] = 'C';
            }
        }
        ans += (j - i + 1) / 2;
        i = j;
      }
    } else {
      int count;
      vector<char> b = a;
      int countA = 0, countB = 1;
      if (a[0] != 'A')
        b[0] = 'A';
      else
        b[0] = 'B';
      for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
          a[i] = 'A' + !(a[i] - 'A');
          countA++;
        }
        if (b[i] == b[i - 1]) {
          b[i] = 'A' + !(b[i] - 'A');
          countB++;
        }
      }
      if (countA > countB) {
        cout << countB << endl;
        cout << b;
        return 0;
      } else {
        cout << countA << endl;
        cout << a;
        return 0;
      }
    }
  } else {
    if (a[0] == a[1]) {
      ans = 1;
      if (a[0] != 'A')
        a[0] = 'A';
      else
        a[0] = 'B';
    }
  }
  cout << ans << endl;
  cout << a;
  return 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  for (long long i = 0; i < t; i++) solve();
  return 0;
}