鬼子进村

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》,剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队,于是独立团与鬼子展开游击战。

题目描述

描述 县城里有n个用地道相连的房子,第i个只与第i-1和第i+1个相连。这是有m个消息依次传来 1、消息为D x:鬼子将x号房子摧毁了,地道被堵上。 2、消息为R :村民们将鬼子上一个摧毁的房子修复了。 3、消息为Q x:有一名士兵被围堵在x号房子中。 李云龙收到信息很紧张,他想知道每一个被围堵的士兵能够到达的房子有几个。

输入输出格式

输入格式


第一行2个整数n,m(n,m<=50000)。 接下来m行,有如题目所说的三种信息共m条。

输出格式


对于每一个被围堵的士兵,输出该士兵能够到达的房子数。

输入输出样例

输入样例 #1

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

输出样例 #1

1
0
2
4

说明

若士兵被围堵在摧毁了的房子中,那只能等死了。。。。。。