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;
long long mult(long long a, long long b, long long p = 1000000007) {
  return ((a % p) * (b % p)) % p;
}
long long add(long long a, long long b, long long p = 1000000007) {
  return (a % p + b % p) % p;
}
long long fpow(long long n, long long k, long long p = 1000000007) {
  long long r = 1;
  for (; k; k >>= 1LL) {
    if (k & 1LL) r = mult(r, n, p);
    n = mult(n, n, p);
  }
  return r;
}
long long inv(long long a, long long p = 1000000007) {
  return fpow(a, p - 2, p);
}
void self_max(int &a, int &b) { a = max(a, b); }
void self_min(int &a, int &b) { a = min(a, b); }
bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
const long long sizes = 1e7 + 1;
std::vector<long long> vec;
long long n, m, k, o, p;
long long dp[sizes];
void solve() {
  cin >> n >> k;
  string str;
  cin >> str;
  long long ans = 0;
  if (n == 1) {
    cout << 0 << '\n';
    cout << str << '\n';
    ;
    return;
  }
  if (k > 2) {
    for (int i = 1; i < str.length() - 1; i++) {
      if (str[i] == str[i - 1]) {
        ans++;
        if (str[i - 1] != 'A' && str[i + 1] != 'A') {
          str[i] = 'A';
        } else if (str[i - 1] != 'B' && str[i + 1] != 'B') {
          str[i] = 'B';
        } else if (str[i - 1] != 'C' && str[i + 1] != 'C') {
          str[i] = 'C';
        }
      }
    }
    int ia = str.length() - 1;
    if (str[ia] == str[ia - 1]) {
      ans++;
      if (str[ia - 1] != 'A') {
        str[ia] = 'A';
      } else if (str[ia - 1] != 'B') {
        str[ia] = 'B';
      } else if (str[ia - 1] != 'C') {
        str[ia] = 'C';
      }
    }
  } else {
    long long a = 0;
    long long b = 0;
    long long c = 0;
    long long d = 0;
    for (int i = 0; str[i]; ++i) {
      if ((i + 1) % 2 == 1) {
        if (str[i] == 'A')
          a++;
        else
          b++;
      } else {
        if (str[i] == 'B')
          a++;
        else
          b++;
      }
    }
    char ch;
    if (a < b) {
      ans = a;
      ch = 'B';
    } else {
      ans = b;
      ch = 'A';
    }
    for (int i = 0; str[i]; ++i) {
      str[i] = ch;
      if (ch == 'A')
        ch = 'B';
      else
        ch = 'A';
    }
  }
  cout << ans << '\n';
  cout << str << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  int p = t;
  while (t--) {
    solve();
  }
}