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:  Application x generates a notification (this new notification is unread).  Thor reads all notifications generated so far by application x (he may re-read some notifications).  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.


-----Examples-----
Input
3 4
1 3
1 1
1 2
2 3

Output
1
2
3
2

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

Output
1
2
3
0
1
2



-----Note-----

In the first sample:  Application 3 generates a notification (there is 1 unread notification).  Application 1 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads the notification generated by application 3, there are 2 unread notifications left. 

In the second sample test:  Application 2 generates a notification (there is 1 unread notification).  Application 4 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left.  Application 3 generates a notification (there is 1 unread notification).  Application 3 generates a notification (there are 2 unread notifications).

Difficulty: competition

Starter code:

Solutions:
#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import sys,collections
n,q=list(map(int,input().split()))
M=collections.defaultdict(collections.deque)
Q=collections.deque()
L=[]
s=n=m=0
for _ in range(q):
	y,x=list(map(int,input().split()))
	if 2>y:
		s+=1
		Q.append(x)
		M[x].append(n)
		n+=1
	elif 3>y:
		y=M.get(x)
		if y:
			s-=len(y)
			del M[x]
	else:
		while x>m:
			z=Q.popleft()
			y=M.get(z)
			if y and y[0]<x:
				s-=1
				y.popleft()
				if not y:del M[z]
			m+=1
	L.append(s)
sys.stdout.write('\n'.join(map(str,L)))


#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import collections
n,q=list(map(int,input().split()))
M=collections.defaultdict(collections.deque)
Q=collections.deque()
L=[]
s=n=m=0
for _ in range(q):
	y,x=list(map(int,input().split()))
	if 2>y:
		s+=1
		Q.append(x)
		M[x].append(n)
		n+=1
	elif 3>y:
		y=M.get(x)
		if y:
			s-=len(y)
			del M[x]
	else:
		while x>m:
			z=Q.popleft()
			y=M.get(z)
			if y and y[0]<x:
				s-=1
				y.popleft()
				if not y:del M[z]
			m+=1
	L.append(s)
print('\n'.join(map(str,L)))


#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import collections
n,q=list(map(int,input().split()))
Q=collections.deque()
A=n*[0]
B=A[:]
L=[]
s=n=0
for _ in range(q):
	y,x=list(map(int,input().split()))
	if 2>y:
		x-=1
		Q.append(x)
		B[x]+=1
		A[x]+=1
		s+=1
	elif 3>y:
		x-=1
		s-=A[x]
		A[x]=0
	else:
		while x>n:
			n+=1
			y=Q.popleft()
			B[y]-=1
			if(B[y]<A[y]):
				A[y]-=1
				s-=1
	L.append(s)
print('\n'.join(map(str,L)))


#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import collections
n,q=list(map(int,input().split()))
Q=collections.deque()
A=n*[0]
B=A[:]
L=[]
s=n=0
for _ in range(q):
	y,x=list(map(int,input().split()))
	if 2>y:
		x-=1
		Q.append(x)
		B[x]+=1
		A[x]+=1
		s+=1
	elif 3>y:
		x-=1
		s-=A[x]
		A[x]=0
	else:
		while x>n:
			n+=1
			y=Q.popleft()
			B[y]-=1
			if(B[y]<A[y]):
				A[y]-=1
				s-=1
	L.append(str(s))
print('\n'.join(L))


n,q = map(int,input().split())
xi = [[0]*(n+1) for i in range(2)]
noti = []
ans = ""
num = 0
num2 = 0
num3 = 0
while q > 0:
    typ,xt = map(int,input().split())
    if typ == 1:
        xi[0][xt] += 1
        noti += [xt]
        num += 1
        num2 += 1
    elif typ == 3:
        for i in range(num3,xt):
            if i+1 > xi[1][noti[i]]:
                xi[0][noti[i]] -= 1
                num -= 1
        num3 = max(num3,xt)
    else:
        num -= xi[0][xt]
        xi[0][xt] = 0
        xi[1][xt] = num2
    ans += str(num)
    ans += "\n"
    q -= 1
print(ans)

def main():
    n, q = list(map(int, input().split()))
    vol, tot, l, res = [0] * (n + 1), [0] * (n + 1), [], []
    z = m = 0
    for _ in range(q):
        t, x = list(map(int, input().split()))
        if t == 1:
            l.append(x)
            tot[x] += 1
            vol[x] += 1
            z += 1
        elif t == 2:
            z -= vol[x]
            vol[x] = 0
        else:
            if m < x:
                r, m = list(range(m, x)), x
                for i in r:
                    x = l[i]
                    tot[x] -= 1
                    if vol[x] > tot[x]:
                        vol[x] -= 1
                        z -= 1
        res.append(z)
    print('\n'.join(map(str, res)))


def __starting_point():
    main()

__starting_point()

n , q = map(int, input().split())
stacks = [[] for i in range(n + 1)]
queue = []
q_start = 0
unread = 0
ans = []

for i in range(q):
    action, num = map(int, input().split())
    if action == 1:
        queue.append(0)
        stacks[num].append(len(queue) - 1)
        unread += 1
        
    elif action == 2:
        for i in range(len(stacks[num])):
            if stacks[num][i] >= q_start and queue[stacks[num][i]] == 0:
                queue[stacks[num][i]] = 1
                unread -= 1
        stacks[num] = []
    else:
        for i in range(q_start, num):
            if queue[i] == 0:
                queue[i] = 1
                unread -= 1
        q_start = max(q_start, num)
    ans.append(unread)

print("\n".join(map(str, ans)))

from sqlite3 import collections
n, q = list(map(int, input().split()))
Q = collections.deque()
A = n*[0]
B = A[: ]
L = []
s=n=0
for _ in range(q):
    y, x = list(map(int, input().split()))
    if y<2 :
        x-=1
        Q.append(x)
        B[x]+=1
        A[x]+=1
        s+=1
    elif y<3 :
        x-=1
        s-=A[x]
        A[x]=0
    else :
        while x>n :
            n+=1
            y=Q.popleft()
            B[y]-=1
            if B[y]<A[y] :
                A[y]-=1
                s-=1
    L.append(str(s))
print('\n'.join(L))


import collections
n, q = list(map(int ,input().split()))
Q = collections.deque()
A = [0] * n
B = A[:]
L = []
s = n = 0
for k in range(q):
    type1, x = list(map(int, input().split()))
    if type1 == 1:
        x -= 1
        Q.append(x)
        B[x] += 1
        A[x] += 1
        s += 1
    if type1 == 2:
        x -= 1
        s -= A[x]
        A[x] = 0
    if type1 == 3:
        while x > n:
            n += 1
            y = Q.popleft()
            B[y] -= 1
            if B[y] < A[y]:
                A[y] -= 1
                s -= 1
    L.append(str(s))
print('\n'.join(L))


n,q = map(int, input().split())
l = []
a = [[] for _ in range(n)]
tp = 0
ans = 0
anss = []
for i in range(q):
    x,b = map(int, input().split())
    if x == 1:
        l.append(1)
        a[b-1].append(len(l) -1)
        ans +=1
    elif x == 2:
        while len(a[b-1]) > 0:
            z = a[b-1].pop()
            ans -= l[z]
            l[z] = 0
    else:
        while tp < b:
            ans -=l[tp]
            l[tp] = 0
            tp += 1
    anss.append(str(ans))
print('\n'.join(anss))

import collections 
n,q=map(int,input().split())
dq=collections.deque()
l=n*[0]
p=list(l)
ans=0
t=0
ansl=[]
while(q):
    a,b=map(int,input().split())
    if a==1:
        dq.append(b-1)
        l[b-1],p[b-1]=l[b-1]+1,p[b-1]+1
        ans=ans+1
    elif a==2:
        ans=ans-l[b-1]
        l[b-1]=0
    else:
        while b>t:
            t=t+1
            j=dq.popleft()
            p[j]=p[j]-1
            if l[j]>p[j]:
                l[j]=l[j]-1
                ans=ans-1
    ansl.append(str(ans))        
    q=q-1
print("\n".join(ansl))    

#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import collections
n,q=list(map(int,input().split()))
Q=collections.deque()
A=n*[0]
B=A[:]
L=[]
s=n=0
for _ in range(q):
	y,x=list(map(int,input().split()))
	if 2>y:
		x-=1
		Q.append(x)
		B[x]+=1
		A[x]+=1
		s+=1
	elif 3>y:
		x-=1
		s-=A[x]
		A[x]=0
	else:
		while x>n:
			n+=1
			y=Q.popleft()
			B[y]-=1
			if(B[y]<A[y]):
				A[y]-=1
				s-=1
	L.append(s)
print('\n'.join(map(str,L)))




# Made By Mostafa_Khaled


#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import sys,collections
n,q=map(int,input().split())
M=collections.defaultdict(collections.deque)
Q=collections.deque()
L=[]
s=n=m=0
for _ in range(q):
	y,x=map(int,input().split())
	if 2>y:
		s+=1
		Q.append(x)
		M[x].append(n)
		n+=1
	elif 3>y:
		y=M.get(x)
		if y:
			s-=len(y)
			del M[x]
	else:
		while x>m:
			z=Q.popleft()
			y=M.get(z)
			if y and y[0]<x:
				s-=1
				y.popleft()
				if not y:del M[z]
			m+=1
	L.append(s)
sys.stdout.write('\n'.join(map(str,L)))


import sys
import collections
n, q = list(map(int, input().split()))

# Key: app number, value: list of indexes in the arr
M = collections.defaultdict(collections.deque)

# arr = []
Q = collections.deque()
n = 0
s = 0
m = 0
L = []
for i in range(q):
  c, x = list(map(int, input().split()))

  if c == 1:
    # if x not in M:
    #   M[x] = collections.deque()
      # M[x] = set()

    # M[x].add(n)
    M[x].append(n)
    Q.append(x)

    n += 1
    s += 1

    # print("case 1")

  elif c == 2:
    y = M.get(x)
    if y:
      s -= len(y)

      del M[x]

    # print("case 2")

  else:
    while x > m:
      z = Q.popleft()
      y = M.get(z)
      if y and y[0] < x:
        s -= 1
        y.popleft()

        if not y:
          del M[z]
        # M[app].remove(message)

      m += 1
    # print("case 3")
  L.append(s)
sys.stdout.write('\n'.join(map(str, L)))

# for i in range(q):
#   c, x = map(int, input().split())

#   if c == 1:
#     if x not in hash:
#       hash[x] = collections.deque()
#       # hash[x] = set()

#     # hash[x].add(messageNumber)
#     hash[x].append(messageNumber)
#     deque.append((x, messageNumber))

#     messageNumber += 1
#     unread += 1

#     # print("case 1")
#     print(unread)

#   elif c == 2:
#     if x in hash:
#       xUnread = len(hash[x])
#       hash[x] = set()
#       unread -= xUnread
#     # print("case 2")
#     print(unread)

#   else:
#     t = x
#     read = 0
#     while len(deque) != 0 and deque[0][1] <= t:
#       app, message = deque.popleft()

#       if message in hash[app]:
#         read += 1
#         hash[app].remove(message)

#     unread -= read

#     # print("case 3")
#     print(unread)


import sys
import collections
n, q = list(map(int, input().split()))

# Key: app number, value: list of indexes in the arr
M = {}

# arr = []
Q = collections.deque()
n = 1
s = 0
m = 0
L = []
for i in range(q):
  c, x = list(map(int, input().split()))

  if c == 1:
    if x not in M:
      M[x] = collections.deque()
      # M[x] = set()

    # M[x].add(n)
    M[x].append(n)
    Q.append(x)

    n += 1
    s += 1

    # print("case 1")

  elif c == 2:
    if x in M:
      s -= len(M[x])

      M[x] = collections.deque()

    # print("case 2")

  else:
    while x > m:
      z = Q.popleft()

      if z in M and len(M[z]) > 0 and M[z][0] <= x:
        s -= 1
        M[z].popleft()
        # M[app].remove(message)

      m += 1
    # print("case 3")
  L.append(s)
sys.stdout.write('\n'.join(map(str, L)))
# for i in range(q):
#   c, x = map(int, input().split())

#   if c == 1:
#     if x not in hash:
#       hash[x] = collections.deque()
#       # hash[x] = set()

#     # hash[x].add(messageNumber)
#     hash[x].append(messageNumber)
#     deque.append((x, messageNumber))

#     messageNumber += 1
#     unread += 1

#     # print("case 1")
#     print(unread)

#   elif c == 2:
#     if x in hash:
#       xUnread = len(hash[x])
#       hash[x] = set()
#       unread -= xUnread
#     # print("case 2")
#     print(unread)

#   else:
#     t = x
#     read = 0
#     while len(deque) != 0 and deque[0][1] <= t:
#       app, message = deque.popleft()

#       if message in hash[app]:
#         read += 1
#         hash[app].remove(message)

#     unread -= read

#     # print("case 3")
#     print(unread)


import collections
import sys

n, q = list(map(int, input().split()))
# Key: app number, value: list of indexes in the arr
hash = {}

# arr = []
deque = collections.deque()
messageNumber = 1
unread = 0
L = []

for i in range(q):
  c, x = list(map(int, input().split()))

  if c == 1:
    if x not in hash:
      hash[x] = set()

    hash[x].add(messageNumber)
    deque.append((x, messageNumber))

    messageNumber += 1
    unread += 1

    # print("case 1")
    # print(unread)

  elif c == 2:
    if x in hash:
      xUnread = len(hash[x])
      hash[x] = set()
      unread -= xUnread
    # print("case 2")
    # print(unread)

  else:
    t = x
    read = 0
    while len(deque) != 0 and deque[0][1] <= t:
      app, message = deque.popleft()

      if message in hash[app]:
        read += 1
        hash[app].remove(message)

    unread -= read

    # print("case 3")
    # print(unread)
  L.append(unread)
sys.stdout.write('\n'.join(map(str, L)))


import collections
import sys

n, q = map(int, input().split())
# Key: app number, value: list of indexes in the arr
hash = {}

deque = collections.deque()
messageNumber = 1
unread = 0
L = []

for i in range(q):
  c, x = map(int, input().split())

  if c == 1:
    if x not in hash:
      hash[x] = set()

    hash[x].add(messageNumber)
    deque.append((x, messageNumber))

    messageNumber += 1
    unread += 1


  elif c == 2:
    if x in hash:
      xUnread = len(hash[x])
      hash[x] = set()
      unread -= xUnread


  else:
    t = x
    read = 0
    while len(deque) != 0 and deque[0][1] <= t:
      app, message = deque.popleft()

      if message in hash[app]:
        read += 1
        hash[app].remove(message)

    unread -= read


  L.append(unread)
print('\n'.join(map(str, L)))

import sys
n,m=list(map(int,input().split()))
k=0
pos=0
L=[]
L1=[]
d={i:[0,-1] for i in range(1,n+1)}
for i in range(m) :
    a,b=list(map(int,input().split()))
    if a==1 :
        d[b][0]+=1
        
        k+=1
        L.append(b)
    elif a==2 :
        k-=d[b][0]
        d[b][0]=0
        d[b][1]=len(L)
    else :
        for j in range(pos,b) :
            
            if d[L[j]][0]>0 and d[L[j]][1]<j+1   :
                
                k-=1
                d[L[j]][0]-=1
                
        pos=max(pos,b)
    L1.append(k)
sys.stdout.write('\n'.join(map(str,L1)))
    
    
            
            
            
        
        
        


import sys
n,m=list(map(int,input().split()))
k=0
pos=0
L=[]
L1=[]
d={i:[0,-1] for i in range(1,n+1)}
for i in range(m) :
    a,b=list(map(int,sys.stdin.readline()[:-1].split()))
    if a==1 :
        d[b][0]+=1
        
        k+=1
        L.append(b)
    elif a==2 :
        k-=d[b][0]
        d[b][0]=0
        d[b][1]=len(L)
    else :
        for j in range(pos,b) :
            
            if d[L[j]][0]>0 and d[L[j]][1]<j+1   :
                
                k-=1
                d[L[j]][0]-=1
                
        pos=max(pos,b)
    L1.append(k)
sys.stdout.write('\n'.join(map(str,L1)))
    
    
            
            
            
        
        
        


'''input
4 6
1 2
1 4
1 2
3 3
1 3
1 3


'''

n, q = list(map(int, input().split()))

count = [0 for i in range(n + 1)]
queue = []
read = set()
unread = 0
ans = []
last_q_idx = 0
last_app_idx = [1 for i in range(n + 1)]

for i in range(q):
    action, num = list(map(int, input().split()))
    if action == 1:
        queue.append((num, count[num] + 1))
        count[num] += 1
        unread += 1
    elif action == 2:
        for number in range(last_app_idx[num], count[num] + 1):
            if (num, number) not in read:
                read.add((num, number))
                unread -= 1
        last_app_idx[num] = max(last_app_idx[num], count[num])
    else:
        for idx in range(last_q_idx, num):
            app, number = queue[idx]
            if (app, number) not in read:
                read.add((app, number))
                last_app_idx[app] = max(last_app_idx[app], number)
                unread -= 1
        last_q_idx = max(last_q_idx, num)
    # print(action, num, last_q_idx, last_app_idx, queue)
    ans.append(unread)
 
print("\n".join(map(str, ans)))




import sys,collections
n,q=map(int,input().split())
M=collections.defaultdict(collections.deque)
Q=collections.deque()
L=[]
s=n=m=0
for _ in range(q):
	y,x=map(int,input().split())
	if 2>y:
		s+=1
		Q.append(x)
		M[x].append(n)
		n+=1
	elif 3>y:
		y=M.get(x)
		if y:
			s-=len(y)
			del M[x]
	else:
		while x>m:
			z=Q.popleft()
			y=M.get(z)
			if y and y[0]<x:
				s-=1
				y.popleft()
				if not y:del M[z]
			m+=1
	L.append(s)
sys.stdout.write('\n'.join(map(str,L)))

import sys, collections
def inp():
    return map(int, input().split())
n, q = inp()
Q = collections.deque()
A = n * [0]
B = A[:]
L = []
s = n = 0
for _ in range(q):
    typeq, x = inp()
    if typeq == 1:
        x -= 1
        Q.append(x)
        B[x] += 1
        A[x] += 1
        s += 1
    elif typeq == 2:
        x -= 1
        s -= A[x]
        A[x] = 0
    else:
        while x > n:
            n += 1
            y = Q.popleft()
            B[y] -= 1
            if (B[y] < A[y]):
                A[y] -= 1
                s -= 1
    L.append(s)
sys.stdout.write('\n'.join(map(str,L)))

from sys import stdin
input = stdin.readline

n, q, = list(map(int, input().split()))
arr = [tuple(map(int, input().split())) for _ in range(q)]
adj = [[] for _ in range(n+1)]
curr, cnt, res, vis = 0, 0, [], []
 
for t, v in arr:
    if t == 1:
        adj[v].append(len(vis))
        vis.append(0)
        cnt += 1
    elif t == 2:
        for u in adj[v]:
            if not vis[u]:
                vis[u] = 1
                cnt -= 1
        adj[v] = []
    else:
        while v > curr:
            if not vis[curr]:
                vis[curr] = 1
                cnt -= 1
            curr += 1
    res.append(cnt)
print('\n'.join(map(str, res)))


import sys
input = sys.stdin.readline

n, q = map(int, input().split())
l = [[] for _ in range(n)]
is_read = []
is_read_idx = 0
ans = 0
prev_t = 0

for _ in range(q):
    ty, v = map(int, input().split())
    
    if ty==1:
        l[v-1].append(is_read_idx)
        is_read_idx += 1
        is_read.append(False)
        ans += 1
    elif ty==2:
        for idx in l[v-1]:
            if not is_read[idx]:
                is_read[idx] = True
                ans -= 1
        
        l[v-1] = []
    else:
        if v>prev_t:
            for idx in range(prev_t, v):
                if not is_read[idx]:
                    is_read[idx] = True
                    ans -= 1
                
            prev_t = v
        
    print(ans)