Description
Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, … L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:

1. “C A B C” Color the board from segment A to segment B with color C.
2. “P A B” Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, … color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains “C A B C” or “P A B” (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output
Ouput results of the output operation in order, each line contains a number.

Sample Input
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

Sample Output
2
1

这道题开始尝试线段树存30个值,表示区间内每个颜色的数量
，果然T了,然后用二进制存值,区间颜色总数可以通过二进制上一的数量得出,区间直接取值直接与运算完直接返回即可,要加lazy take。

注意:不要用流输入和流输出,流输入和流输出在POJ上面巨慢。血的教训!!!

代码如下:

#include<stdio.h>
#include <algorithm>

const int N = 1e5 + 5e1;
int num[N << 3];
int lazy[N << 3];
int n, t, o;

inline void push_up(int x) {
    num[x] = num[x << 1] | num[x << 1 | 1];
}

inline void push_down(int x) {
    if (lazy[x] != 0) {
        lazy[x << 1] = lazy[x << 1 | 1] = lazy[x];
        num[x << 1] = num[x << 1 | 1] = lazy[x];
        lazy[x] = 0;
    }
}

inline void build(int l = 1, int r = n, int x = 1) {
    if (l == r) {
        num[x] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    push_up(x);
}

inline void update(int ql, int qr, int nl, int nr, int val, int x) {
    if (nl >= ql && nr <= qr) {
        lazy[x] = val;
        num[x] = val;
        return;
    }
    push_down(x);
    int mid = (nl + nr) >> 1;
    if (mid >= ql) {
        update(ql, qr, nl, mid, val, x << 1);
    }
    if (mid < qr) {
        update(ql, qr, mid + 1, nr, val, x << 1 | 1);
    }
    push_up(x);
}

inline int query(int ql, int qr, int nl = 1, int nr = n, int x = 1) {
    if (nl > qr || nr < ql)return 0;
    if (ql <= nl && qr >= nr) {
        return num[x];
    }
    push_down(x);
    int mid = (nl + nr) >> 1;
    int l = 0, r = 0;
    if (mid >= ql) {
        l = query(ql, qr, nl, mid, x << 1);
    }
    if (mid < qr) {
        r = query(ql, qr, mid + 1, nr, x << 1 | 1);
    }
    return (l | r);
}

signed main(int argc, char **argv) {
    scanf("%d %d %d", &n, &t, &o);
    build();
    for (int i = 1; i <= o; i++) {
        char op[2];
        scanf("%s", op);
        if (op[0] == 'C') {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            if (a > b) {
                std::swap(a, b);
            }
            update(a, b, 1, n, (1 << (c - 1)), 1);
        } else {
            int a, b;
            scanf("%d %d", &a, &b);
            if (a > b) {
                std::swap(a, b);
            }
            int maxn = 0;
            int res = query(a, b);
            while (res > 0) {
                if (res & 1)maxn++;
                res >>= 1;
            }
            printf("%d\n", maxn);
        }
    }
    return 0;
}