Time Limit: 2 seconds
Memory Limit: 256 megabytes
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:
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.
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 typei — type of the i-th event. If typei = 1 or typei = 2 then it is followed by an integer xi. Otherwise it is followed by an integer ti (1 ≤ typei ≤ 3, 1 ≤ xi ≤ n, 1 ≤ ti ≤ q).
In the first sample:
In the second sample test: