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;
const long long int MOD = 1000000000 + 7;
const long long int MOD1 = 998244353;
long long int pwr(long long int a, long long int b) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a *= a;
    b >>= 1;
  }
  return res;
}
long long int strTo(string s) {
  stringstream tmp(s);
  long long int x = 0;
  tmp >> x;
  return x;
}
string NoTo(long long int n) {
  ostringstream str1;
  str1 << n;
  string ans = str1.str();
  return ans;
}
vector<bool> sieve(1000001, true);
void Sieve() {
  sieve[0] = false;
  sieve[1] = false;
  for (long long int i = 2; i * i <= 1000000; i++) {
    if (sieve[i] == true) {
      for (long long int j = i * i; j <= 1000000; j += i) sieve[j] = false;
    }
  }
}
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  for (long long int i = (long long int)0; i < (long long int)r; i++) {
    ans = (ans * (n - i));
    ans = (ans / (i + 1));
  }
  return ans;
}
long long int pwrm(long long int a, long long int b, long long int m) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
bool sortinrev(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.first > b.first);
}
bool cmp(pair<long long int, pair<long long int, long long int>> p1,
         pair<long long int, pair<long long int, long long int>> p2) {
  if (p1.first == p2.first) {
    if (p1.second.first < p2.second.first)
      return true;
    else
      return false;
  }
  return (p1.first > p2.first);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  if (k == 2) {
    string t1 = "", t2 = "";
    for (long long int i = (long long int)0; i < (long long int)n; i++) {
      if (i % 2 == 0) {
        t1 += "A";
        t2 += "B";
      } else {
        t1 += "B";
        t2 += "A";
      }
    }
    long long int ct1 = 0, ct2 = 0;
    for (long long int i = (long long int)0; i < (long long int)n; i++) {
      if (s[i] != t1[i]) ct1++;
      if (s[i] != t2[i]) ct2++;
    }
    if (ct1 < ct2)
      cout << ct1 << "\n" << t1 << "\n";
    else
      cout << ct2 << "\n" << t2 << "\n";
  } else {
    long long int ans = 0;
    long long int ctr = 1;
    vector<pair<long long int, long long int>> an;
    long long int lf = 0;
    for (long long int i = (long long int)0; i < (long long int)n - 1; i++) {
      if (s[i] == s[i + 1])
        ctr++;
      else {
        if (ctr > 1) {
          ans += ctr / 2;
          an.push_back({lf, i});
          ctr = 1;
          lf = i;
        }
        lf++;
      }
    }
    if (ctr > 1) {
      ans += ctr / 2;
      an.push_back({lf, n - 1});
      ctr = 1;
    }
    for (long long int i = (long long int)0; i < (long long int)an.size();
         i++) {
      long long int st = an[i].first;
      long long int en = an[i].second;
      char ch;
      if (en < n - 1) ch = s[en + 1];
      long long int ct = 0;
      char ch1 = s[st];
      char ch2;
      for (long long int l = (long long int)0; l < (long long int)26; l++) {
        char tp = char(l + 65);
        if (tp != ch && tp != ch1) {
          ch2 = tp;
          break;
        }
      }
      for (long long int j = (long long int)st; j < (long long int)en + 1;
           j++) {
        if (ct % 2 != 0) s[j] = ch2;
        ct++;
      }
    }
    cout << ans << "\n";
    cout << s << "\n";
  }
  cerr << "Time Elapsed : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}