题目描述

众所周知，徐老师开了一家旅馆，旅馆有 $n$ 间房间，编号从 $1$ 到 $n$

在寒假期间，徐老师的旅馆接受了 $T$ 家旅行社的住宿要求，这些旅行社带的旅游团都很奇怪，他们每次带团来入住时，一定要住指定编号的连续房间

例如一个旅游团要求住 $[5,9]$ 编号的房间，就是要求住 $5,6,7,8,9$ 这五个房间

但是显然这样的要求总是会碰到冲突，而后来的旅游团总是财大气粗，他们想要住的房间如果之前已经有其他旅客入住了，那么他们会出高价要求这些房间的旅客搬去其他旅馆！

也就是说如果有两个旅游团，第一个旅游团要求住 $[5,9]$，第二个旅游团要求住 $[4,6]$，那么第二个旅游团会出高价让 $5,6$ 两个房间的旅客搬走

也就是在这两个旅游团入住后，$4,5,6$ 房间住的是第二个旅游团的旅客，$7,8,9$ 房间住的是第一个旅游团的旅客

现在徐老师想让 wjw 完成一个程序，因为入住信息很多，徐老师想随时可以知道现在旅馆内有多少家旅行社的客人

P.S.1 同一家旅行社可能会有好几个旅行团

P.S.2 为了方便计算，徐老师会认为空房间也是一家旅行社的客人

输入格式

输入第一行包含三个整数 $n,T,m$，表示有 $n$ 个房间，$T$ 家旅游团，以及 $m$ 次事件（事件包含两种：旅游团入住和徐老师的询问）

接下来 $m$ 行，每行表示一次事件，以下为两种事件的格式

1. C l r id 表示一次入住，表示编号为 $id$ 的旅行社有一个旅游团要入住 $[l,r]$ 编号的房间
2. Q l r 表示徐老师的一次查询，询问 $[l,r]$ 编号的房间内有多少个不同的旅行社的客人（注意同一家旅行社不同的旅行团的客人也是同一家旅行社的）

输出格式

对于每次询问，输出一个整数表示答案

数据范围

对于 $10\%$ 的数据满足： $1 \leq n,m \leq 1000, T = 1$

对于 $30\%$ 的数据满足： $1 \leq n,m \leq 1000$

对于 $100\%$ 的数据满足： $1 \leq n,m \leq 10^5, T \leq 30, 1 \leq x \leq y \leq n, id \leq T$

样例输入

5 3 6
C 1 3 2
Q 1 5
C 2 4 1
Q 1 5
C 3 5 3
Q 1 5

样例输出

2
3
3

样例解释

以下过程用编号代表每个房间入住的旅客所在的旅行社

一开始五个房间分别为 $[0,0,0,0,0]$

第一次入住后分别为 $[2,2,2,0,0]$

第二次入住后分别为 $[2,1,1,1,0]$

第三次入住后分别为 $[2,1,3,3,3]$