题目描述

（可能无关紧要的地方有点漏洞，但不会影响题意）

雷神常常要去地球，所以洛基给她一款智能手机作为礼物。手机上安装了n款应用，每款应用都会跳出很多消息，在每一单位时间，会发生以下3种事件之一：

• 1. 第x个应用跳出了一条消息
• 2. 雷神读了第x个应用跳出的所有消息
• 3. 雷神读了所有应用跳出的前x条消息

雷神很不喜欢手机上有一堆“99+”，所以她希望知道，每一分钟后有多少条新消息未读。

输入格式

第一行2个整数n,q表示应用的数目和事件总数

输出格式

共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$，且保证每个事件合法。

样例

3 4
1 3
1 1
1 2
2 3

1
2
3
2

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

1
2
3
0
1
2