题目描述

今天是牛牛的生日，牛牛请了他的好朋友们一起过生日，生日必不可少的环节当然就是吃蛋糕啦。

由于有 $n$ 个人来参加牛牛的生日，牛牛需要给 $n$ 个人分蛋糕,

牛牛有 $2$ 种操作：

$C$ $l,r,x$ 将 $[l,r]$ 的人的蛋糕数改成 $x(1 \le x \le k)$。

$P$ $l,r$ 查询 $[l,r]$ 中有多少种不同的蛋糕数。

牛牛总共执行了 $m$ 次这样的操作，请输出所有的询问操作所对应的答案。

你可以认为初始时每个人有 $1$ 块蛋糕。

输入格式

第一行三个数 $n,m,k$。

接下来 $m$ 行,每行一次操作,含义见题目描述。

输出格式

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

样例

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

2
1

数据范围

对于 $30\%$ 的数据: $n,m\le 1000$ 。

对于 $50\%$ 的数据: $n,m\le 5\times 10^4$ 。

对于 $100\%$的数据: $1\le l \le r \le n \le 10^5$ , $1\le m \le 10^5$, $1\le k \le 30$ 。