托尔正在适应地球。洛基送给他一部智能手机作为礼物。该手机上有 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 个未读通知)。