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 N = 2e5;
const long long int INF = 1e18;
const long long int mod = 1e9 + 7;
long long int n, k;
long long int vis[N];
string second;
map<long long int, char> m;
char calc(long long int i, long long int j) {
  for (long long int h = 1; h <= k; h++) {
    if (second[i] != m[h] && second[j] != m[h]) {
      return m[h];
    }
  }
}
char one(long long int i) {
  for (long long int j = 1; j <= k; j++) {
    if (second[i] != m[j]) {
      return m[j];
    }
  }
}
int main() {
  cin >> n >> k >> second;
  if (k == 2) {
    string x = "\0", x2 = "\0";
    for (long long int i = 1; i <= n; i++) {
      if (i % 2) {
        x += 'A';
      } else {
        x += 'B';
      }
    }
    for (long long int i = 1; i <= n; i++) {
      if (i % 2) {
        x2 += 'B';
      } else {
        x2 += 'A';
      }
    }
    long long int xcnt = 0, x2cnt = 0;
    for (long long int i = 0; i < n; i++) {
      if (second[i] != x[i]) {
        xcnt++;
      }
    }
    for (long long int i = 0; i < n; i++) {
      if (second[i] != x2[i]) {
        x2cnt++;
      }
    }
    if (xcnt > x2cnt) {
      cout << x2cnt << endl;
      cout << x2 << endl;
    } else {
      cout << xcnt << endl;
      cout << x << endl;
    }
  } else {
    long long int ans = 0;
    char x = 'A';
    for (long long int i = 1; i <= 26; i++) {
      m[i] = x;
      x++;
    }
    for (long long int i = 1; i < n; i++) {
      if (second[i] == second[i - 1]) {
        if (i + 1 < n) {
          second[i] = calc(i - 1, i + 1);
        } else {
          second[i] = one(i - 1);
        }
        ans++;
      }
    }
    cout << ans << endl;
    cout << second << endl;
  }
}