题目背景

小明正在看一部战争题材的电视剧。剧中，一支小分队在一个小镇与敌军展开了激烈的拉锯战。

题目描述

小镇里有 $n$ 座用地下通道相连的房屋，第 $i$ 座只与第 $i-1$ 和第 $i+1$ 座相连。特别地，第 $1$ 座房屋只和第 $2$ 座连通，第 $n$ 座房屋只和第 $n-1$ 座连通。现在有 $m$ 条情报依次传来：

1. 若情报为 <code>D x</code>：敌军将 $x$ 号房屋炸毁了，通道被堵上。

2. 若情报为 <code>R</code>：友军将敌军上一个炸毁的房屋修复了。

3. 若情报为 <code>Q x</code>：有一名士兵被困在 $x$ 号房屋中。

现定义能够到达如下：若存在房屋 $i,j(1\leq i\leq j\leq n)$，使得对于任意的 $k(i\leq k\leq j)$ 都满足房屋 $k$ 未被炸毁，则称房屋 $i$ 与房屋 $j$ 互相能够到达。

指挥官收到情报很紧张，他想知道每一个被困的士兵能够到达的房屋有几个。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，有如题目所说的三种情报共 $m$ 条。

输出格式

对于每一个被困的士兵，输出该士兵能够到达的房屋数。

样例

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

1
0
2
4

提示

$1\leq n,m\leq 5\times 10^4$。

若士兵被困在已被炸毁的房屋中，那就只能等支援了。