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;
template <typename T>
T gcd(T a, T b) {
  if (a % b) return gcd(b, a % b);
  return b;
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
vector<string> tokenizer(string str, char ch) {
  std::istringstream var((str));
  vector<string> v;
  string t;
  while (getline((var), t, (ch))) {
    v.push_back(t);
  }
  return v;
}
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cout << *it << " = " << a << "\n";
  err(++it, args...);
}
void file_i_o() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int main(int argc, char const *argv[]) {
  clock_t begin = clock();
  file_i_o();
  long long int n;
  int k;
  cin >> n >> k;
  string s;
  cin >> s;
  long long int cnt = 0;
  if (n == 2) {
    if (s[0] == s[1]) {
      string st = "";
      for (int i = (0); i <= (k - 1); i++) {
        if (char(i + 65) != s[0]) {
          st += char(i + 65);
          break;
        }
      }
      st += s[1];
      cout << 1 << "\n";
      cout << st << "\n";
    } else {
      cout << 0 << "\n";
      cout << s << "\n";
    }
  } else if (n == 1) {
    cout << 0 << "\n";
    cout << s << "\n";
  } else if (k == 2) {
    long long int cnt1 = 0;
    long long int cnt2 = 0;
    string t1 = "";
    string t2 = "";
    for (long long int i = 0; i < s.size(); i++) {
      if (i % 2 == 0) {
        t1 += "A";
      } else {
        t1 += "B";
      }
    }
    for (long long int i = 0; i < s.size(); i++) {
      if (i % 2 == 0) {
        t2 += "B";
      } else {
        t2 += "A";
      }
    }
    for (int i = (0); i <= (s.size() - 1); i++) {
      if (t1[i] != s[i]) {
        cnt1 += 1;
      } else {
        cnt2 += 1;
      }
    }
    if (cnt1 < cnt2) {
      cout << cnt1 << "\n";
      cout << t1 << "\n";
    } else {
      cout << cnt2 << "\n";
      cout << t2 << "\n";
    }
  } else {
    s += "0";
    for (long long int i = 1; i < s.size(); i++) {
      if (s[i] == s[i - 1]) {
        for (int j = (0); j <= (k - 1); j++) {
          if (char(j + 65) != s[i - 1] and char(j + 65) != s[i + 1]) {
            s[i] = char(j + 65);
          }
        }
        cnt += 1;
      }
    }
    cout << cnt << "\n";
    for (long long int i = 0; i < s.size() - 1; i++) {
      cout << s[i] << "";
    }
  }
  return 0;
}