4345. 地道战

抗日战争时期,地道战在华北平原广大地区广泛开展。

有 $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