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;
string str;
int dp[500007][28];
int n, k;
int solve(int pos, int prev) {
  if (pos > str.size()) {
    return 0;
  }
  if (dp[pos][prev] != -1) {
    return dp[pos][prev];
  }
  int ret = 1 << 29;
  int ch = str[pos] - 65;
  if (ch != prev) {
    ret = min(ret, solve(pos + 1, ch));
  }
  for (int i = 0; i < k; i++) {
    if (i == ch || i == prev) {
      continue;
    }
    ret = min(ret, 1 + solve(pos + 1, i));
  }
  return dp[pos][prev] = ret;
}
void path(int pos, int prev) {
  if (pos == str.size()) {
    return;
  }
  int ch = str[pos] - 65;
  if (ch != prev && dp[pos][prev] == dp[pos + 1][ch]) {
    char c = ch + 65;
    cout << c;
    path(pos + 1, ch);
    return;
  } else {
    for (int i = 0; i < k; i++) {
      if (i == ch || i == prev) {
        continue;
      }
      if (dp[pos + 1][i] + 1 == dp[pos][prev]) {
        char c = i + 'A';
        cout << c;
        path(pos + 1, i);
        return;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  cin >> str;
  memset(dp, -1, sizeof(dp));
  k = min(k, 10);
  int ans = solve(0, 27);
  cout << ans << endl;
  path(0, 27);
  return 0;
}