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>
#pragma optimize("", off)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:36777216")
const long long inf = 0x3f3f3f3f3f3f3f3LL;
const long long mod = 1e9 + 7;
using namespace std;
template <class T>
void smin(T& a, T val) {
  if (a > val) a = val;
}
template <class T>
void smax(T& a, T val) {
  if (a < val) a = val;
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  bool first = true;
  os << "[";
  for (auto i : v) {
    if (!first) os << ", ";
    os << i;
    first = false;
  }
  return os << "]";
}
const long long N = 2 * 1e5 + 10;
long long n, k;
string s;
void solve() {
  string tmp = s;
  long long cost1 = 0;
  for (char i = 'A'; i < (char)('A' + k); ++i) {
    if (i != tmp[1]) {
      cost1++;
      tmp[0] = i;
      break;
    }
  }
  for (long long i = 1; i < n; ++i) {
    if (tmp[i] != tmp[i - 1]) {
      continue;
    }
    cost1++;
    for (char j = 'A'; j < (char)('A' + k); ++j) {
      if (j != tmp[i + 1] and j != tmp[i - 1]) {
        tmp[i] = j;
        break;
      }
    }
  }
  string tmp2 = s;
  long long cost2 = 0;
  for (char i = 'A'; i < (char)('A' + k); ++i) {
    if (i != tmp2[0]) {
      cost2++;
      tmp2[1] = i;
      break;
    }
  }
  for (long long i = 1; i < n; ++i) {
    if (tmp2[i] != tmp2[i - 1]) {
      continue;
    }
    cost2++;
    for (char j = 'A'; j < (char)('A' + k); ++j) {
      if (j != tmp2[i + 1] and j != tmp2[i - 1]) {
        tmp2[i] = j;
        break;
      }
    }
  }
  if (cost1 < cost2) {
    cout << cost1 << '\n';
    cout << (tmp).substr(0, n);
    return;
  } else {
    cout << cost2 << '\n';
    cout << (tmp2).substr(0, n);
    return;
  }
}
void solve2() {
  string tmp = s;
  char ch = 'A';
  long long cost = 0;
  for (long long i = 0; i < n; ++i) {
    if (tmp[i] != ch) {
      tmp[i] = ch;
      cost++;
    }
    if (ch == 'A') {
      ch = 'B';
    } else {
      ch = 'A';
    }
  }
  long long cost2 = 0;
  string tmp2 = s;
  ch = 'B';
  for (long long i = 0; i < n; ++i) {
    if (tmp2[i] != ch) {
      tmp2[i] = ch;
      cost2++;
    }
    if (ch == 'A') {
      ch = 'B';
    } else {
      ch = 'A';
    }
  }
  if (cost < cost2) {
    cout << cost << '\n';
    cout << tmp;
    return;
  } else {
    cout << cost2 << '\n';
    cout << tmp2;
    return;
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k;
  cin >> s;
  if (n == 1) {
    cout << 0 << '\n';
    cout << s;
    return 0;
  }
  if (k == 2) {
    solve2();
    return 0;
  }
  s += '#';
  if (s[0] == s[1]) {
    solve();
    return 0;
  }
  long long cost = 0;
  for (long long i = 1; i < n; ++i) {
    if (s[i] != s[i - 1]) {
      continue;
    }
    cost++;
    for (char j = 'A'; j < (char)('A' + k); ++j) {
      if (j != s[i + 1] and j != s[i - 1]) {
        s[i] = j;
        break;
      }
    }
  }
  cout << cost << '\n';
  cout << s.substr(0, n);
  return 0;
}