作为国家的管理者，小 x 新开拓的有 $n$ 做城池，这 $n$ 座城池排成一条直线，依次编号为 $1 \sim n$，初始时对于所有 $i \in [1,n-1]$ 城市 $i$ 到城市 $i+1$ 有单向道路。

每个城市都有一个等级 A 或者 B，A 级市更高一些，所以按理来说应该拥有更多的人口。不过有的 A 级市可以通过道路到达人口更多的 B 级市，那么这个 A 级市就有被降级的危险，我们称这个 A 级市是危险的。

现在小 x 列出了一系列改造计划，希望你能实时跟进这些计划，并时刻告诉他有多少个 A 级城市是危险的。

改造计划有两种：

$\texttt{UPDATE x y}$： 人口迁移政策，把第 $x$ 个城市的人口修改为 $y$。

$\texttt{REVERSE l r}$： 道路修改计划，把第 $l$ 个城市到第 $r$ 个城市之间的道路全部翻转（每条道路改变朝向，而不是拿出一条链反过来接回去）。

对于每个计划，输出一行一个正整数表示修改之后危险的 A 级城市的数目。

输入格式

第一行两个正整数 $n, Q$ 表示城市数和询问数。

接下来 $n$ 行，每行一个整数和一个字符（只能是$\texttt{A,B}$） $P_i, c$，表示每个城市的人口和等级。

接下来 $Q$ 行，每行如下：

$\texttt{UPDATE x y}$

$\texttt{REVERSE l r}$

如题意表示一次改造。

输出格式

对于每个操作输出一行一个整数表示答案。

样例一

input

7 4
0 A
13 B
4 B
11 B
10 A
12 B
4 A
REVERSE 2 5
UPDATE 5 12
REVERSE 5 7
UPDATE 2 0

output

2
2
3
1

样例二

见样例数据下载。

限制与约定

本题采用捆绑测试，对于全部数据，$1 \leq N,Q \leq 10^5; 1 \leq x \leq n; 1 \leq l \leq r \leq n; 0 \leq P_i,y \leq 75.$

时间限制：$4\texttt{s}$

空间限制：$233\texttt{MB}$

下载

样例数据下载