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 mod = 1e9 + 7;
const int inf = 1e9 + 9;
const long long MOD = 1e9 + 696969;
const long long INF = 1e18;
int n, m, k, a, b, c, w, h;
char s[1000100];
int dp[1000100][26], last[1000100][26];
pair<int, int> SECOND, MIN;
inline pair<int, int> minexc(int x) {
  if (x != MIN.second) return MIN;
  return SECOND;
}
char ret[1000100];
int main() {
  scanf("%d%d", &n, &k) ?: 0;
  scanf("%s", s + 1) ?: 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j < k; ++j) dp[i][j] = inf;
  MIN = {0, -1};
  SECOND = {0, 0};
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < k; ++j)
      if (s[i] == (char)j + 'A') {
        dp[i][j] = minexc(j).first;
        last[i][j] = minexc(j).second;
      } else
        dp[i][j] = minexc(j).first + 1, last[i][j] = minexc(j).second;
    MIN = {inf, inf};
    SECOND = {inf, inf};
    for (int j = 0; j < k; ++j)
      if (dp[i][j] < MIN.first) {
        SECOND = MIN;
        MIN = make_pair(dp[i][j], j);
      } else if (dp[i][j] < SECOND.first)
        SECOND = make_pair(dp[i][j], j);
  }
  int res = inf, poz = inf;
  for (int i = 0; i < k; ++i)
    if (dp[n][i] < res) res = dp[n][i], poz = i;
  cout << res << endl;
  if (res == 0) {
    for (int i = 1; i <= n; ++i) printf("%c", s[i]);
    exit(0);
  }
  for (int i = n; i > 0; --i) {
    ret[i] = poz + 'A';
    poz = last[i][poz];
  }
  for (int i = 1; i <= n; ++i) printf("%c", ret[i]);
}