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[500001][30], pre[500001][30];
int main(int argc, const char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k, A[500001], i, j, c, l;
  string S;
  cin >> n >> k;
  cin >> S;
  for (i = 0; i < n; i++) A[i + 1] = S[i] - 'A';
  for (i = 0; i <= n; i++)
    for (j = 0; j <= k; j++) dp[i][j] = 1e7;
  for (i = 1; i <= n; i++) {
    for (j = 0; j < k; j++) {
      if (i == 1) {
        dp[i][j] = ((j == A[i]) ? (0) : (1));
        pre[i][j] = -1;
        continue;
      }
      c = (j == A[i]) ? 0 : 1;
      for (l = 0; l < k; l++) {
        if (l != j) {
          if (dp[i][j] > c + dp[i - 1][l]) {
            pre[i][j] = l;
            dp[i][j] = c + dp[i - 1][l];
          }
        }
      }
    }
  }
  int m = 1e7, p = -1;
  for (j = 0; j < k; j++) {
    if (m > dp[n][j]) {
      m = dp[n][j];
      p = j;
    }
  }
  cout << m << "\n";
  stack<char> St;
  i = n;
  while (p != -1) {
    St.push(char(p + 'A'));
    p = pre[i][p];
    i--;
  }
  char q;
  while (!St.empty()) {
    q = St.top();
    cout << q;
    St.pop();
  }
  return 0;
}