← 返回题目列表

Codeforces · 704/A

A. 雷神

中文机器翻译题面 查看原题

托尔正在适应地球。洛基送给他一部智能手机作为礼物。该手机上有 n 个应用程序。托尔对这款手机很着迷。他只有一个小问题:他无法计算这些应用程序生成的未读通知的数量(也许 Loki 对它施了诅咒,所以他不能计算)。

q 事件即将发生(按时间顺序)。它们分为三种类型:

1. 应用程序 x 生成通知(此新通知未读)。
2. Thor 读取应用程序 x 目前生成的所有通知(他可能会重新读取一些通知)。
3. Thor 读取电话应用程序生成的前 t 个通知(在第一类型的前 t 个事件中生成的通知)。保证在该事件之前至少存在t个第一类型的事件。请注意,他不会读取第一个未读通知,他只是读取手机上生成的第一个通知,并且在此操作中他可能会重新阅读其中的一些通知。

请帮助托尔并告诉他每次事件后未读通知的数量。您可能会假设最初手机中没有任何通知。

输入

输入的第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 300 000) — 申请数量和要发生的事件数量。

接下来的 q 行包含事件。这些行中的第 i 行以整数 typei 开头 - 第 i 个事件的类型。如果 typei = 1 或 typei = 2,则后面跟着一个整数 xi。否则后跟整数 ti (1 ≤ typei ≤ 3, 1 ≤ xi ≤ n, 1 ≤ ti ≤ 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

注意

在第一个示例中:

1. 应用程序 3 生成通知(有 1 个未读通知)。
2. 应用程序 1 生成通知(有 2 个未读通知)。
3. 应用程序 2 生成通知(有 3 个未读通知)。
4. Thor 读取了应用程序 3 生成的通知,还剩 2 个未读通知。

在第二个样本测试中:

1. 应用程序 2 生成通知(有 1 个未读通知)。
2. 应用程序 4 生成通知(有 2 个未读通知)。
3. 应用程序 2 生成通知(有 3 个未读通知)。
4. Thor 阅读了前三个通知,由于到目前为止只有三个通知,因此不会剩下未读的通知。
5. 应用程序 3 生成通知(有 1 个未读通知)。
6. 应用程序 3 生成通知(有 2 个未读通知)。