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 main() {
  int n, k;
  scanf("%d", &n);
  scanf("%d", &k);
  string s;
  cin >> s;
  int len = s.size();
  if (k == 2) {
    int cnt1 = 0;
    int cnt2 = 0;
    string s1 = "", s2 = "";
    for (int i = (0); i < (len); ++i) {
      if (i % 2) {
        cnt1 += (s[i] == 'A' ? 0 : 1);
        s1 += 'A';
      } else {
        cnt1 += (s[i] == 'B' ? 0 : 1);
        s1 += 'B';
      }
    }
    for (int i = (0); i < (len); ++i) {
      if (i % 2) {
        cnt2 += (s[i] == 'B' ? 0 : 1);
        s2 += 'B';
      } else {
        cnt2 += (s[i] == 'A' ? 0 : 1);
        s2 += 'A';
      }
    }
    cout << (cnt1 <= cnt2 ? cnt1 : cnt2) << endl;
    cout << (cnt1 <= cnt2 ? s1 : s2) << endl;
  } else {
    int cnt = 0;
    char strt = s[0];
    string ans = "";
    string temp = "";
    temp += strt;
    for (int i = (1); i < (len); ++i) {
      if (s[i] == strt) {
        temp += strt;
      } else {
        int l = temp.size();
        if (l % 2) {
          int j = 0;
          for (j = (0); j < (26); ++j) {
            if (j != (int)(strt - 'A')) {
              break;
            }
          }
          for (int i = 1; i < l; i += 2) {
            temp[i] = (char)('A' + j);
            cnt++;
          }
          ans += temp;
        } else {
          int j = 0;
          for (j = (0); j < (26); ++j) {
            if (j != (int)(strt - 'A') && j != int(s[i] - 'A')) {
              break;
            }
          }
          for (int i = l - 1; i >= 0; i -= 2) {
            temp[i] = (char)('A' + j);
            cnt++;
          }
          ans += temp;
        }
        strt = s[i];
        temp = "";
        temp += strt;
      }
    }
    int l = temp.size();
    if (l % 2) {
      int j = 0;
      for (j = (0); j < (26); ++j) {
        if (j != (int)(strt - 'A')) {
          break;
        }
      }
      for (int i = 1; i < l; i += 2) {
        cnt++;
        temp[i] = (char)('A' + j);
      }
      ans += temp;
    } else {
      int j = 0;
      for (j = (0); j < (26); ++j) {
        if (j != (int)(strt - 'A')) {
          break;
        }
      }
      for (int i = l - 1; i >= 0; i -= 2) {
        cnt++;
        temp[i] = (char)('A' + j);
      }
      ans += temp;
    }
    cout << cnt << endl;
    cout << ans << endl;
  }
  return 0;
}