Thor

题意翻译

(可能无关紧要的地方有点漏洞,但不会影响题意) 【题目描述】 雷神常常要去地球,所以洛基给**她**一款智能手机作为礼物。手机上安装了n款应用,每款应用都会跳出很多消息,在每一单位时间,会发生以下3种事件之一: - 1) 第x个应用跳出了一条消息 - 2) 雷神读了第x个应用跳出的所有消息 - 3) 雷神读了所有应用跳出的前x条消息 雷神很不喜欢手机上有一堆“99+”,所以**她**希望知道,每一分钟后有多少条新消息未读。 【输入格式】 第一行2个整数n,q表示应用的数目和事件总数 接下来有q行,每行2个整数i,x表示发生事件i(i=1,2,3即与题目描述中的序号对应)和事件中的x 【输出格式】 共q行,每行一个整数表示每个事件发生后有多少未读消息 【输入样例1】 ``` 3 4 1 3 1 1 1 2 2 3 ``` 【输出样例1】 ``` 1 2 3 2 ``` 【输入样例2】 ``` 4 6 1 2 1 4 1 2 3 3 1 3 1 3 ``` 【输出样例2】 ``` 1 2 3 0 1 2 ``` 【数据范围】 对于100%的数据,满足$1<=n,q<=300000$,且保证每个事件合法。

题目描述

Thor is getting used to the Earth. As a gift Loki gave him a smartphone. There are $ n $ applications on this phone. Thor is fascinated by this phone. He has only one minor issue: he can't count the number of unread notifications generated by those applications (maybe Loki put a curse on it so he can't). $ q $ events are about to happen (in chronological order). They are of three types: 1. Application $ x $ generates a notification (this new notification is unread). 2. Thor reads all notifications generated so far by application $ x $ (he may re-read some notifications). 3. Thor reads the first $ t $ notifications generated by phone applications (notifications generated in first $ t $ events of the first type). It's guaranteed that there were at least $ t $ events of the first type before this event. Please note that he doesn't read first $ t $ unread notifications, he just reads the very first $ t $ notifications generated on his phone and he may re-read some of them in this operation. Please help Thor and tell him the number of unread notifications after each event. You may assume that initially there are no notifications in the phone.

输入输出格式

输入格式


The first line of input contains two integers $ n $ and $ q $ ( $ 1<=n,q<=300000 $ ) — the number of applications and the number of events to happen. The next $ q $ lines contain the events. The $ i $ -th of these lines starts with an integer $ type_{i} $ — type of the $ i $ -th event. If $ type_{i}=1 $ or $ type_{i}=2 $ then it is followed by an integer $ x_{i} $ . Otherwise it is followed by an integer $ t_{i} $ ( $ 1<=type_{i}<=3,1<=x_{i}<=n,1<=t_{i}<=q $ ).

输出格式


Print the number of unread notifications after each event.

输入输出样例

输入样例 #1

3 4
1 3
1 1
1 2
2 3

输出样例 #1

1
2
3
2

输入样例 #2

4 6
1 2
1 4
1 2
3 3
1 3
1 3

输出样例 #2

1
2
3
0
1
2

说明

In the first sample: 1. Application $ 3 $ generates a notification (there is $ 1 $ unread notification). 2. Application $ 1 $ generates a notification (there are $ 2 $ unread notifications). 3. Application $ 2 $ generates a notification (there are $ 3 $ unread notifications). 4. Thor reads the notification generated by application $ 3 $ , there are $ 2 $ unread notifications left. In the second sample test: 1. Application $ 2 $ generates a notification (there is $ 1 $ unread notification). 2. Application $ 4 $ generates a notification (there are $ 2 $ unread notifications). 3. Application $ 2 $ generates a notification (there are $ 3 $ unread notifications). 4. Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left. 5. Application $ 3 $ generates a notification (there is $ 1 $ unread notification). 6. Application $ 3 $ generates a notification (there are $ 2 $ unread notifications).