DH的新手机Ⅱ

题目描述

DH觉得之前那个DS手机不好用，又换了一部新手机，这个新手机什么都好，就是没办法知道有多少条未读信息，现在他请你帮忙写个程序告诉他手机上有多少条未读信息。

这部手机上安装了$n$个应用程序，刚开始没有信息，下面会发生$q$个事件，事件属于以下三种类型之一：

1、 $x$号应用程序出现了一条新信息（未读的）。

2、 DH阅读了$x$号应用程序至今的所有信息（他可能重复读了某些信息）。

3、 DH阅读了最开始的$t$个信息（由第1种事件产生的最开始的$t$个信息），保证在此之前由第1种事件产生的信息至少有$t$个。需要注意的是他不是阅读前$t$个未读信息，他读的是最开始的$t$个信息，所以他可能会重复阅读某些信息。

请你告诉DH每一个事件发生后手机上未读信息的数量。

输入

多组输入数据。

对于每组数据，第一行有两个整数$n,q(1 \leq n,q \leq 300000)$，表示应用程序数量和事件数量，接下来$q$行，每一行两个整数，第一个整数是$type_i$，如果$type_i=1$或$type_i=2$，第二个数为$x_i$，否则第二个数为$t_i$$(1 \leq type_i \leq 3,1 \leq x_i \leq n,1 \leq t_i \leq q)$。

输出

对于每组数据，输出$q$行，每一行一个整数，第$i$行表示第$i$个事件发生完了以后未读信息的数量。

输入样例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