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;
int dp[500005][30];
char cdp[500005][30], Ans[500005];
pair<int, char> Min, Min2;
struct byINT {
  bool operator()(const pair<int, char>& a, const pair<int, char>& b) {
    return a.first > b.first;
  }
};
int main() {
  int len, col, Count = 0;
  char Str[500005];
  scanf("%d %d", &len, &col);
  scanf("%s", Str);
  for (int i = 0; i < col; ++i) {
    if (Str[0] != i + 'A') {
      dp[0][i] = 1;
      if (Min2.first == 0) {
        Min2.first = 1;
        Min2.second = i + 'A';
      }
    }
  }
  Min.first = 0;
  Min.second = Str[0];
  for (int i = 1; i < len; ++i) {
    priority_queue<pair<int, char>, vector<pair<int, char> >, byINT> pq;
    for (int j = 0; j < col; ++j) {
      if (Str[i] == j + 'A') {
        if (Min.second != j + 'A') {
          dp[i][j] = Min.first;
          cdp[i][j] = Min.second;
        } else {
          dp[i][j] = Min2.first;
          cdp[i][j] = Min2.second;
        }
      } else {
        if (Min.second != j + 'A') {
          dp[i][j] = Min.first + 1;
          cdp[i][j] = Min.second;
        } else {
          dp[i][j] = Min2.first + 1;
          cdp[i][j] = Min2.second;
        }
      }
      pq.push(make_pair(dp[i][j], j + 'A'));
    }
    Min.first = pq.top().first;
    Min.second = pq.top().second;
    pq.pop();
    Min2.first = pq.top().first;
    Min2.second = pq.top().second;
  }
  Count = Min.first;
  char Now = Min.second;
  Ans[len] = NULL;
  for (int i = len - 1; i >= 0; --i) {
    Ans[i] = Now;
    Now = cdp[i][Now - 'A'];
  }
  printf("%d\n%s", Count, Ans);
  return 0;
}