You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

小明最近购买了一款新型智能手机，手机上安装了n个社交应用。这些应用会不断推送通知消息，为了帮助小明管理这些通知，系统在每一分钟会记录以下3种操作之一：

1. 第x个应用推送了一条新通知
2. 小明清空了第x个应用的所有通知
3. 小明清除了所有应用中最旧的x条通知（按全局接收顺序）

小明希望随时了解当前未读通知的数量，请你设计一个程序，在每次操作后输出剩余未读通知的总数。

Format

Input

第一行包含两个整数n和q，分别表示应用数量和操作总数

接下来q行，每行描述一个操作：

• 操作1格式为"1 x"，表示第x个应用收到新通知
• 操作2格式为"2 x"，表示清空第x个应用的所有通知
• 操作3格式为"3 x"，表示清除全局最早接收的x条通知

Output

共q行，每行一个整数表示每次操作后剩余的未读通知数量

Samples

样例输入 1

3 4
1 3
1 1
1 2
2 3

样例输出 1

1
2
3
2

样例解释 1

应用3生成一条通知（此时有1条未读通知）。

应用1生成一条通知（此时有2条未读通知）。

应用2生成一条通知（此时有3条未读通知）。

小明清除了应用3的通知，剩余2条未读通知。

样例输入 2

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

样例输出 2

1
2
3
0
1
2

样例解释 2

应用2生成一条通知（此时有1条未读通知）。

应用4生成一条通知（此时有2条未读通知）。

应用2再次生成一条通知（此时有3条未读通知）。

小明清除了最早收到的3条通知，由于当前总共只有3条通知，因此所有通知都被清除（剩余0条未读）。

应用3生成一条通知（此时有1条未读通知）。

应用3再次生成一条通知（此时有2条未读通知）。

Limitation

对于$30\%$的数据，保证$1 \leq n,q \leq 100$，且所有操作均合法。

对于$100\%$的数据，保证$1 \leq n,q \leq 300000， 1 \leq x \leq n$，且所有操作均合法。