Thor is getting used to the Earth. As a gift Loki gave him a smartphone. There are _n_ applications on this phone. Thor is fascinated by this phone. He has only one minor issue: he can't count the number of unread notifications generated by those applications (maybe Loki put a curse on it so he can't).
_q_ events are about to happen (in chronological order). They are of three types:
1. Application _x_ generates a notification (this new notification is unread).
2. Thor reads all notifications generated so far by application _x_ (he may re-read some notifications).
3. Thor reads the first _t_ notifications generated by phone applications (notifications generated in first _t_ events of the first type). It's guaranteed that there were at least _t_ events of the first type before this event. Please note that he doesn't read first _t_ unread notifications, he just reads the very first _t_ notifications generated on his phone and he may re-read some of them in this operation.
Please help Thor and tell him the number of unread notifications after each event. You may assume that initially there are no notifications in the phone.
## Input
The first line of input contains two integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 300 000) — the number of applications and the number of events to happen.
The next _q_ lines contain the events. The _i_\-th of these lines starts with an integer _type__i_ — type of the _i_\-th event. If _type__i_ = 1 or _type__i_ = 2 then it is followed by an integer _x__i_. Otherwise it is followed by an integer _t__i_ (1 ≤ _type__i_ ≤ 3, 1 ≤ _x__i_ ≤ _n_, 1 ≤ _t__i_ ≤ _q_).
## Output
Print the number of unread notifications after each event.
[samples]
## Note
In the first sample:
1. Application 3 generates a notification (there is 1 unread notification).
2. Application 1 generates a notification (there are 2 unread notifications).
3. Application 2 generates a notification (there are 3 unread notifications).
4. Thor reads the notification generated by application 3, there are 2 unread notifications left.
In the second sample test:
1. Application 2 generates a notification (there is 1 unread notification).
2. Application 4 generates a notification (there are 2 unread notifications).
3. Application 2 generates a notification (there are 3 unread notifications).
4. Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left.
5. Application 3 generates a notification (there is 1 unread notification).
6. Application 3 generates a notification (there are 2 unread notifications).
索尔正在适应地球生活。作为礼物，洛基送给他一部智能手机。这部手机上有 #cf_span[n] 个应用程序。索尔对这部手机着迷，但他有一个小问题：他无法统计这些应用程序生成的未读通知数量（也许洛基施了咒语，让他无法统计）。
将发生 #cf_span[q] 个事件（按时间顺序）。事件共有三种类型：
请帮助索尔，在每次事件后告诉他未读通知的数量。你可以假设初始时手机中没有任何通知。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n, q ≤ 300 000]）——应用程序的数量和将要发生的事件数量。
接下来的 #cf_span[q] 行包含事件。第 #cf_span[i] 行以一个整数 #cf_span[typei] 开头——表示第 #cf_span[i] 个事件的类型。如果 #cf_span[typei = 1] 或 #cf_span[typei = 2]，则后面跟着一个整数 #cf_span[xi]；否则后面跟着一个整数 #cf_span[ti]（#cf_span[1 ≤ typei ≤ 3, 1 ≤ xi ≤ n, 1 ≤ ti ≤ q]）。
请在每次事件后输出未读通知的数量。
在第一个样例中：
在第二个样例测试中：
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n, q ≤ 300 000]）——应用程序的数量和将要发生的事件数量。接下来的 #cf_span[q] 行包含事件。第 #cf_span[i] 行以一个整数 #cf_span[typei] 开头——表示第 #cf_span[i] 个事件的类型。如果 #cf_span[typei = 1] 或 #cf_span[typei = 2]，则后面跟着一个整数 #cf_span[xi]；否则后面跟着一个整数 #cf_span[ti]（#cf_span[1 ≤ typei ≤ 3, 1 ≤ xi ≤ n, 1 ≤ ti ≤ q]）。
## Output
请在每次事件后输出未读通知的数量。
[samples]
## Note
在第一个样例中：
应用程序 #cf_span[3] 生成一条通知（此时有 #cf_span[1] 条未读通知）。
应用程序 #cf_span[1] 生成一条通知（此时有 #cf_span[2] 条未读通知）。
应用程序 #cf_span[2] 生成一条通知（此时有 #cf_span[3] 条未读通知）。
索尔阅读了应用程序 #cf_span[3] 生成的通知，剩下 #cf_span[2] 条未读通知。
在第二个样例测试中：
应用程序 #cf_span[2] 生成一条通知（此时有 #cf_span[1] 条未读通知）。
应用程序 #cf_span[4] 生成一条通知（此时有 #cf_span[2] 条未读通知）。
应用程序 #cf_span[2] 生成一条通知（此时有 #cf_span[3] 条未读通知）。
索尔阅读了前三条通知，由于此时总共只有三条通知，因此没有未读通知剩下。
应用程序 #cf_span[3] 生成一条通知（此时有 #cf_span[1] 条未读通知）。
应用程序 #cf_span[3] 生成一条通知（此时有 #cf_span[2] 条未读通知）。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the number of applications and the number of events, respectively.
Let $ N = (n_1, n_2, \dots, n_n) \in \mathbb{N}^n $ be a vector where $ n_i $ is the number of unread notifications for application $ i $.
Let $ T = (t_1, t_2, \dots, t_q) $ be the sequence of events, where each $ t_i \in \{1, 2, 3\} $.
**Constraints**
1. $ 1 \le n, q \le 300{,}000 $
2. For each event $ i \in \{1, \dots, q\} $:
- If $ t_i = 1 $, then $ x_i \in \{1, \dots, n\} $: increment $ n_{x_i} \leftarrow n_{x_i} + 1 $
- If $ t_i = 2 $, then $ x_i \in \{1, \dots, n\} $: set $ n_{x_i} \leftarrow 0 $
- If $ t_i = 3 $, then $ t_i \in \{1, \dots, q\} $: set $ n_j \leftarrow 0 $ for all $ j \in \{1, \dots, n\} $ such that the event index $ \le t_i $
**Objective**
After each event $ i \in \{1, \dots, q\} $, output the total number of unread notifications:
$$
S_i = \sum_{j=1}^{n} n_j
$$