抗日战争时期,地道战在华北平原广大地区广泛开展。
有 $n$ 个村庄排成一排,依次编号 $1 \sim n$。
初始时,任意两个相邻村庄之间可以通过地道保持连通。
接下来共发生了 $m$ 个事件,事件分为以下三种:
D x
,鬼子袭击第 $x$ 个村庄,如果第 $x$ 个村庄的地道完好,则将其毁掉。被毁掉地道的村庄无法通往其他村庄,反之亦然。Q x
,八路军司令询问从第 $x$ 个村庄可以到达多少个地道完好的村庄(包括第 $x$ 个村庄本身)。R
,八路军战士来到鬼子最近一次袭击的村庄,如果该村庄的地道被毁坏,则将地道修好。
对于所有的询问事件,请你做出回答。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行描述一个事件,格式如题面所述。
输出格式
每个询问输出一行回答。
数据范围
每个输入最多包含 $10$ 组数据。
$1 \le n,m \le 50000$,
$1 \le x \le n$。
地道已被毁坏的村庄仍可能受到袭击。
输入样例:
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
输出样例:
1
0
2
4