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 int N = 5e5, inf = 1e9, NIL = -1;
int n, k;
string s;
vector<char> ans;
int memo[N][30];
int dp(int i = 0, int j = 0) {
  if (i == n) return 0;
  int &ret = memo[i][j];
  if (~ret) return ret;
  ret = inf;
  if (i and s[i] - 'A' + 1 != j)
    ret = dp(i + 1, s[i] - 'A' + 1);
  else
    for (int c = 1; c <= k; ++c)
      if (c != j) ret = min(ret, dp(i + 1, c) + (c != s[i] - 'A' + 1));
  return ret;
}
void build(int i = 0, int j = 0) {
  if (i == n) return;
  int &ret = memo[i][j];
  if (i and s[i] - 'A' + 1 != j and ret == dp(i + 1, s[i] - 'A' + 1)) {
    ans.emplace_back(s[i]);
    build(i + 1, s[i] - 'A' + 1);
  } else {
    for (int c = 1; c <= k; ++c)
      if (c != j and dp(i + 1, c) + (c != s[i] - 'A' + 1) == ret) {
        ans.emplace_back(char(c + 'A' - 1));
        build(i + 1, c);
        return;
      }
  }
}
int main() {
  ios_base::sync_with_stdio();
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k >> s;
  memset(memo, NIL, sizeof memo);
  cout << dp() << endl;
  build();
  for (char c : ans) cout << c;
  return 0;
}