dmopc17c4p6 err

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef vector<int> VI;
typedef set<int> SI;
typedef map<int, int> MII;
typedef pair<int,int> PII;

#define MP make_pair
#define A first
#define B second

#define PB push_back
#define FR(i, a, b) for(int i=(a); i<(b); i++)
#define FOR(i, n) FR(i, 0, n)
#define EACH(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)

template <typename T> inline void SetMin(T &a, T b) {if(b < a) a = b;}
template <typename T> inline void SetMax(T &a, T b) {if(b > a) a = b;}

const D EPS = 1e-9;
int EQ(D a, D b) {return fabs(a - b) < EPS;}

typedef complex<D> P;
#define X real
#define Y imag
P GetPoint() {  D x, y; cin >> x >> y; return P(x, y);}
void ShowPoint(P p) {cout << X(p) << "," << Y(p) << "\n";}
D Cross(P a, P b) {return Y(conj(a) * b);}
D Dot(P a, P b) {return X(conj(a) * b);}

const LL M = 1000000007LL;
void Add(LL &a, LL b) {a = (a + b) % M;}
void Mul(LL &a, LL b) {a = (a * b) % M;}
LL Sum(LL a, LL b) {return (a + b) % M;}
LL Prod(LL a, LL b) {return (a * b) % M;}

namespace IO {
   const int BUF = 32768;
   FILE *in = stdin;
   int ipos = BUF;
   char inbuf [BUF];
   inline void init (const char *namein) {
       in = fopen (namein, "r");
   }

   inline char nextc (bool adv = true) {
       if (ipos == BUF) {
           fread (inbuf, sizeof (char), BUF, in);
           ipos = 0;
       }
       return inbuf [adv ? ipos++ : ipos];
   }

   inline void read (int &num) {
       while (nextc (false) != '-' && (nextc (false) < '0' || nextc (false) > '9')) {
           ipos++;
       }

       bool neg = false;
       if (nextc (false) == '-') {
           neg = true;
           ipos++;
       }

       for (num = 0; nextc (false) >= '0' && nextc (false) <= '9';) {
           num = num * 10 + nextc () - '0';
       }

       if (neg) num = -num;
   }

   inline void readch (char &ch) {
       while (nextc (false) < 'A' || nextc (false) > 'Z') {
           ipos++;
       }

       ch = nextc();

   }

}

struct node{
  int m, a, k, i, ma, ak, ki, mak, aki, maki;
  node() {
    m = a = k = i = ma = ak = ki = mak = aki = maki = 0;
  }
};

const int DEP = 18;
const int SIZ = 1<<DEP;

node tree[SIZ * 2];
int len[SIZ * 2];
char marked[SIZ * 2];

int n, q;

void MarkRange(int p, char ch) {
  tree[p] = node();
  if(ch == 'M') tree[p].m = len[p];
  if(ch == 'A') tree[p].a = len[p];
  if(ch == 'K') tree[p].k = len[p];
  if(ch == 'I') tree[p].i = len[p];
  marked[p] = ch;
}

void Down(int p) {
  if(marked[p] != 0) {
    MarkRange(p * 2, marked[p]);
    MarkRange(p * 2 + 1, marked[p]);
    marked[p] = 0;
  }
}

inline void Moo(int &res, int &a, int &b) {
  int k = min(a, b);
  res += k;
  a -= k;
  b -= k;
}

void Merge(node &res, node a, node b) {
  res = node();
  Moo(res.maki, a.mak, b.i);
  Moo(res.maki, a.ma, b.ki);
  Moo(res.maki, a.m, b.aki);
  Moo(res.mak, a.ma, b.k);
  Moo(res.mak, a.m, b.ak);
  Moo(res.aki, a.ak, b.i);
  Moo(res.aki, a.a, b.ki);
  Moo(res.ak, a.a, b.k);
  Moo(res.ki, a.k, b.i);
  Moo(res.ma, a.m, b.a);
  res.m += a.m + b.m;
  res.a += a.a + b.a;
  res.k += a.k + b.k;
  res.i += a.i + b.i;
  res.ma += a.ma + b.ma;
  res.ak += a.ak + b.ak;
  res.ki += a.ki + b.ki;
  res.mak += a.mak + b.mak;
  res.aki += a.aki + b.aki;
  res.maki += a.maki + b.maki;
}

node Query(int p, int l, int r, int l1, int r1) {
  if(l == l1 && r == r1) {
    return tree[p];
  } else {
    node res;
    Down(p);
    int mid = (l + r) / 2;
    if(r1 <= mid) res = Query(p * 2, l, mid, l1, r1);
    else if(mid < l1) res = Query(p * 2 + 1, mid + 1, r, l1, r1);
    else {
      Merge(res, Query(p * 2, l, mid, l1, mid), Query(p * 2 + 1, mid + 1, r, mid + 1, r1));
    }
    return res;
  }
}


void SetRange(int p, int l, int r, int l1, int r1, char ch) {
  if(l == l1 && r == r1) {
    MarkRange(p, ch);
  } else {
    int mid = (l + r) / 2;
    Down(p);
    if(r1 <= mid) SetRange(p * 2, l, mid, l1, r1, ch);
    else if(mid < l1) SetRange(p * 2 + 1, mid + 1, r, l1, r1, ch);
    else {
      SetRange(p * 2, l, mid, l1, mid, ch);
      SetRange(p * 2 + 1, mid + 1, r, mid + 1, r1, ch);
    }
    Merge(tree[p], tree[p * 2], tree[p * 2 + 1]);
  }
}

int main() {
  memset(marked, 0, sizeof(marked));
  FOR(i, SIZ) {
    len[SIZ + i] = 1;
  }
  for(int i = SIZ - 1; i > 0; --i) {
    len[i] = len[i * 2] + len[i * 2 + 1];
  }
  IO::read(n);
  IO::read(q);
  FOR(i, q) {
    int cmd, l, r;
    IO::read(cmd);
    IO::read(l);
    IO::read(r);
//printf("%d %d %d\n", cmd, l, r); fflush(stdout);
    if(cmd == 2) {
      printf("%d\n", Query(1, 1, SIZ, l, r).maki);
    } else {
      char ch;
      IO::readch(ch);
//printf("%c\n", ch);
      SetRange(1, 1, SIZ, l, r, ch);
    }
  }
  return 0;
}