题目限制

1000 ms 128 M

题目描述

今天是牛牛的生日，牛牛请了他的好朋友们一起过生日，生日必不可少的环节当然就是吃蛋糕啦。由于有n个人来参加牛牛的生日，牛牛需要给n个人分蛋糕，牛牛有2种操作

C l r x 将[l,r]的人的蛋糕数改成x(1 <= x <= k)

P l r 查询[l,r]中有多少种不同的蛋糕数
牛牛总共执行了m次这样的操作，请输出所有的询问操作

输入格式

第一行三个数n，m，k。
接下来m行，每行一次操作，含义见题目描述。

输出格式

对于每个询问，输出一行表示答案。

数据范围

对于30%的数据：n,m<=1000。

对于50%的数据：n,m<=50000。

对于100%的数据：1<= l <= r <= n <= 100000,m <= 100000, k <= 30。

输入样例

2 4 2
C 1 1 2
P 1 2
C 2 2 2
P 1 2

输出样例

2
1