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 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).

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:

  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).

Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
import collections
import copy
(n, q) = map(int, input().split())
Q = collections.deque()
A = n * [0]
B = copy.copy(A)
L = []
s = n = 0
for _ in range(q):
	(y, x) = 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))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, Q) = getInts()
	order = dq([])
	cur_total = 0
	cur_del = -1
	els = [0] * (N + 1)
	del_up_to = [-1] * (N + 1)
	for q in range(Q):
		(T, X) = getInts()
		if T == 1:
			order.append(X)
			els[X] += 1
			cur_total += 1
			print(cur_total)
		elif T == 2:
			cur_total -= els[X]
			els[X] = 0
			del_up_to[X] = max(len(order) - 1, del_up_to[X])
			print(cur_total)
		elif T == 3:
			if X - 1 > cur_del:
				for i in range(cur_del + 1, X):
					if del_up_to[order[i]] < i:
						cur_total -= 1
						del_up_to[order[i]] = i
						els[order[i]] -= 1
				cur_del = X - 1
			print(cur_total)
	return
solve()


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))


from collections import defaultdict, deque
q = deque()
(idx, total) = (0, 0)
vis = defaultdict(deque)
not_valid = set()
max_x = -1
ans = []
(N, Q) = map(int, input().split())
for _ in range(Q):
	(t, x) = map(int, input().split())
	if t == 1:
		q.append((idx, x))
		vis[x].append(idx)
		idx += 1
		total += 1
	elif t == 2:
		while vis[x]:
			i = vis[x].pop()
			not_valid.add(i)
			if i <= max_x - 1:
				continue
			total -= 1
	else:
		while q and (q[0][0] <= x - 1 or q[0][0] in not_valid):
			(j, y) = q.popleft()
			if j not in not_valid:
				total -= 1
				vis[y].popleft()
		max_x = max(max_x, x)
	ans.append(str(total))
print('\n'.join(ans))


import math
import sys
import collections
import bisect
import string
import time

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(1):
	(n, q) = get_ints()
	order = collections.deque()
	first = [0] * (n + 1)
	second = [0] * (n + 1)
	ans = []
	counter = 0
	done = 0
	for i in range(q):
		(type, value) = get_ints()
		if type == 1:
			first[value] += 1
			second[value] += 1
			counter += 1
			order.append(value)
		elif type == 2:
			counter -= first[value]
			first[value] = 0
		else:
			while done < value:
				done += 1
				pos = order.popleft()
				second[pos] -= 1
				if second[pos] < first[pos]:
					first[pos] -= 1
					counter -= 1
		ans.append(counter)
	for i in ans:
		print(i)


from collections import deque
from sys import stdin, stdout

def main():
	(n, q) = map(int, stdin.readline().split())
	check = [False] * (3 * 10 ** 5 + 1)
	types = [deque() for _ in range(3 * 10 ** 5 + 1)]
	count = 0
	cn = 1
	queue = deque()
	for _ in range(q):
		(t, v) = map(int, stdin.readline().split())
		if t == 1:
			queue.append(cn)
			count += 1
			types[v].append(cn)
			cn += 1
		elif t == 2:
			while types[v]:
				top = types[v][0]
				if not check[top]:
					check[top] = True
					count -= 1
				types[v].popleft()
		else:
			while queue:
				top = queue[0]
				if top > v:
					break
				elif not check[top]:
					check[top] = True
					count -= 1
				queue.popleft()
		stdout.write(str(count))
		stdout.write('\n')
main()


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
(n, m) = 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) = 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)))


(n, q) = map(int, input().split())
a = [[0] * (n + 1) for i in range(2)]
b = []
n1 = 0
n2 = 0
n3 = 0
k = ''
for i in range(q):
	(typ, x) = map(int, input().split())
	if typ == 1:
		a[0][x] += 1
		b += [x]
		n1 += 1
		n2 += 1
	elif typ == 3:
		for i in range(n3, x):
			if i + 1 > a[1][b[i]]:
				a[0][b[i]] -= 1
				n1 -= 1
		n3 = max(n3, x)
	else:
		n1 -= a[0][x]
		a[0][x] = 0
		a[1][x] = n2
	k += str(n1) + '\n'
print(k)


from collections import defaultdict, deque
import sys
g = defaultdict(list)
(n, q) = map(int, input().split())
ans = 0
k = 1
qu = deque()
an = []
mark = [0] * (q + 1)
for j in range(q):
	(u, v) = map(int, sys.stdin.readline().split())
	if u == 1:
		qu.append((v, k))
		g[v].append(k)
		k = k + 1
		ans += 1
	elif u == 2:
		for i in g[v]:
			if mark[i] == 0:
				mark[i] = 1
				ans -= 1
		g[v] = []
	else:
		while qu and v >= qu[0][1]:
			m = qu.popleft()
			if mark[m[1]] == 0:
				mark[m[1]] = 1
				ans -= 1
	an.append(ans)
print('\n'.join(map(str, an)))


def inp(n):
	if n == 1:
		return map(int, stdin.readline().split())
	elif n == 2:
		return map(float, stdin.readline().split())
	else:
		return map(str, stdin.readline().split())
from sys import stdin
from collections import defaultdict
(n, q) = inp(1)
(total, events, first, c, mem) = (0, defaultdict(int), 1, 1, defaultdict(list))
for i in range(1, q + 1):
	(type, x) = inp(1)
	if type == 1:
		total += 1
		events[c] = x
		mem[x].append(c)
		c += 1
	elif type == 2:
		for j in mem[x][::-1]:
			if events[j]:
				total -= 1
			events[j] = 0
		mem[x] = []
	elif x >= first:
		for j in range(first, x + 1):
			if events[j]:
				total -= 1
				events[j] = 0
		first = x + 1
	print(total)


from collections import deque
import sys
(n, q) = list(map(int, sys.stdin.readline().lstrip().rstrip().split()))
ans = 0
Q = deque()
v1 = [0 for i in range(n)]
v2 = v1[:]
num = 0
temp = []
for i in range(q):
	(a, x) = list(map(int, sys.stdin.readline().lstrip().rstrip().split()))
	if a == 1:
		x -= 1
		ans += 1
		Q.append(x)
		v1[x] += 1
		v2[x] += 1
	elif a == 2:
		x -= 1
		ans -= v1[x]
		v1[x] = 0
	else:
		while x > num:
			num += 1
			y = Q.popleft()
			v2[y] -= 1
			if v1[y] > v2[y]:
				v1[y] -= 1
				ans -= 1
	temp.append(str(ans))
sys.stdout.write('\n'.join(temp))


import sys
input = sys.stdin.buffer.readline
import collections

def solution():
	(n, q) = map(int, input().split())
	Q = collections.deque()
	A = n * [0]
	B = A[:]
	L = []
	s = n = 0
	for _ in range(q):
		(y, x) = 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)))
solution()


import itertools
(n, q) = map(int, input().split())
counterGlob = itertools.count()
Queue = []
StartQ = 0
counter = 0
ans = ''
X = [[] for i in range(n + 1)]
F = [0] * (n + 1)
for i in range(q):
	(typeQ, a) = map(int, input().split())
	if typeQ == 1:
		counter += 1
		ind = next(counterGlob)
		Queue.append(True)
		X[a].append(ind)
	elif typeQ == 2:
		for ind in X[a]:
			if ind >= StartQ and Queue[ind]:
				counter -= 1
				Queue[ind] = False
		X[a] = []
	else:
		for ind in range(StartQ, a):
			if Queue[ind]:
				counter -= 1
				Queue[ind] = False
		StartQ = max(StartQ, a)
	ans += str(counter)
	ans += '\n'
print(ans)


(n, q) = input().split()
n = int(n)
q = int(q)
p0 = 0
Ans = []
Q = [(0, True)]
App = [set() for i in range(n + 1)]
t = 1
ans = 0
for i in range(q):
	(q, p) = input().split()
	p = int(p)
	if q == '1':
		App[p].add(t)
		Q.append([p, False])
		t += 1
		ans += 1
	elif q == '2':
		for i in App[p]:
			Q[i][1] = True
		ans -= len(App[p])
		App[p] = set()
	elif q == '3':
		if p > p0:
			for i in range(p0, p + 1):
				if Q[i][1] == False:
					Q[i][1] = True
					App[Q[i][0]].remove(i)
					ans -= 1
			p0 = p
	Ans.append(ans)
print('\n'.join(map(str, Ans)))


(n, q) = map(int, input().split())
ans = [0] * q
unread = [0] * n
last = [-1] * n
(qur, cur) = ([], 0)
for i in range(q):
	(t, x) = map(int, input().split())
	ans[i] = ans[i - 1]
	if t == 1:
		unread[x - 1] += 1
		ans[i] += 1
		qur.append(x - 1)
	elif t == 2:
		ans[i] -= unread[x - 1]
		unread[x - 1] = 0
		last[x - 1] = len(qur) - 1
	elif x > cur:
		for j in range(cur, x):
			v = qur[j]
			if last[v] < j:
				ans[i] -= 1
				unread[v] -= 1
				last[v] = j
		cur = x
print('\n'.join(map(str, ans)))


import sys
from collections import defaultdict

def main():
	(n, q) = list(map(int, sys.stdin.readline().split()))
	al = 0
	d = defaultdict(list)
	sts = defaultdict(int)
	cur = 0
	msgs = []
	ans = []
	start = 0
	for i in range(q):
		(t, x) = list(map(int, sys.stdin.readline().split()))
		if t == 1:
			al += 1
			d[x].append(al)
			msgs.append(x)
			cur += 1
		elif t == 2:
			size = len(d[x])
			if size > 0:
				cur -= size - sts[x]
				d[x] = list()
				sts[x] = 0
		elif start < x:
			for i in range(start, x):
				v = msgs[i]
				dd = d[v]
				size = len(dd)
				cur_st = sts[v]
				while size > cur_st and dd[cur_st] <= x:
					cur_st += 1
					cur -= 1
				sts[v] = cur_st
			start = x
		ans.append(cur)
	print('\n'.join(map(str, ans)))
main()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections
(n, q) = map(int, input().split())
Q = collections.deque()
A = n * [0]
B = A[:]
L = []
s = n = 0
for _ in range(q):
	(y, x) = 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)))


def main():
	(n, q) = map(int, input().split())
	(vol, tot, l, res) = ([0] * (n + 1), [0] * (n + 1), [], [])
	z = m = 0
	for _ in range(q):
		(t, x) = 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
		elif m < x:
			(r, m) = (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)))
main()


import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
last_2 = [-1] * n
unread_count = [0] * n
total_unread = 0
ev = []
max_3 = 0
ans = []
for i in range(q):
	(t, x) = map(int, input().split())
	x -= 1
	if t == 1:
		ev.append(x)
		unread_count[x] += 1
		total_unread += 1
	elif t == 2:
		total_unread -= unread_count[x]
		unread_count[x] = 0
		last_2[x] = len(ev) - 1
	else:
		for j in range(max_3, x + 1):
			el = ev[j]
			if last_2[el] < j:
				total_unread -= 1
				unread_count[el] -= 1
		max_3 = max(max_3, x + 1)
	ans.append(total_unread)
for a in ans:
	print(a)


import collections
import sys
(n, q) = map(int, input().split())
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)))


(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.append(num)
	q -= 1
print('\n'.join(map(str, ans)))


(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)))


import sys

def main():
	tmp = [int(x) for x in sys.stdin.readline().split()]
	n = tmp[0]
	q = tmp[1]
	readApp = [0] * n
	unreadApp = [0] * n
	unreadTot = 0
	genApp = [0] * n
	firstFlag = 0
	genOps = []
	for i in range(q):
		tmp = [int(x) for x in sys.stdin.readline().split()]
		(ty, x) = (tmp[0], tmp[1])
		if ty == 1:
			x -= 1
			unreadTot += 1
			unreadApp[x] += 1
			genApp[x] += 1
			genOps.append((x, genApp[x]))
		elif ty == 2:
			x -= 1
			unreadTot -= unreadApp[x]
			readApp[x] += unreadApp[x]
			unreadApp[x] = 0
		else:
			for j in range(firstFlag, x):
				(app, index) = (genOps[j][0], genOps[j][1])
				if readApp[app] < index:
					readApp[app] += 1
					unreadApp[app] -= 1
					unreadTot -= 1
			if x > firstFlag:
				firstFlag = x
		print(unreadTot)
main()


from sys import stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
print = stdout.write
(n, q) = map(int, input().split())
d = [[] for i in range(n + 1)]
mark = []
ans = 0
inde = 0
t = 0
for i in range(q):
	(event, x) = map(int, input().split())
	if event == 1:
		ans += 1
		d[x].append(inde)
		inde += 1
		mark.append(False)
	elif event == 2:
		for j in d[x]:
			if not mark[j]:
				mark[j] = True
				ans -= 1
		d[x] = []
	else:
		for j in range(t, x):
			if not mark[j]:
				mark[j] = True
				ans -= 1
		if x > t:
			t = x
	print(str(ans) + '\n')


import sys
import math
from collections import deque
MAXNUM = math.inf
MINNUM = -1 * math.inf

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	for ele in ans:
		sys.stdout.write(str(ele) + '\n')

def solve(n, queries):
	mailbox = [0 for _ in range(n + 1)]
	read = [0 for _ in range(n + 1)]
	tRead = [0 for _ in range(n + 1)]
	queue = deque()
	ans = []
	tCounter = 0
	unread = 0
	for (qType, x) in queries:
		if qType == 1:
			mailbox[x] += 1
			unread += 1
			queue.append(x)
		elif qType == 2:
			unread -= mailbox[x] - read[x]
			read[x] = mailbox[x]
		elif x > tCounter:
			k = x - tCounter
			tCounter = x
			for _ in range(k):
				nxt = queue.popleft()
				tRead[nxt] += 1
				if tRead[nxt] > read[nxt]:
					unread -= tRead[nxt] - read[nxt]
					read[nxt] = tRead[nxt]
		ans.append(unread)
	return ans

def readinput():
	(n, q) = getInts()
	queries = []
	for _ in range(q):
		(a, b) = getInts()
		queries.append((a, b))
	printOutput(solve(n, queries))
readinput()


import sys
import collections
(n, q) = map(int, input().split())
M = {}
Q = collections.deque()
n = 1
s = 0
m = 0
L = []
for i in range(q):
	(c, x) = map(int, input().split())
	if c == 1:
		if x not in M:
			M[x] = collections.deque()
		M[x].append(n)
		Q.append(x)
		n += 1
		s += 1
	elif c == 2:
		if x in M:
			s -= len(M[x])
			M[x] = collections.deque()
	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 += 1
	L.append(s)
sys.stdout.write('\n'.join(map(str, L)))


from collections import deque
from collections import OrderedDict
import math
import sys
import os
from io import BytesIO
input = sys.stdin.readline
(n, q) = map(int, input().split())
arrIdxIsread = [0] * (300000 + 1)
arrInd = [0] * (300000 + 1)
arrDicByAp = [object] * (300000 + 1)
read = 0
readByIdex = 0
arrInd.append(0)
Unread = 0
curentIdex = 0
for i in range(n + 1):
	arrDicByAp[i] = OrderedDict()
for i in range(1, q + 1):
	(t, x) = map(int, input().split())
	if t == 1:
		arrInd[i] = x
		arrDicByAp[x][i] = 0
		Unread += 1
	elif t == 2:
		arrIdxIsread[i] = -1
		for it in arrDicByAp[x]:
			if arrDicByAp[x][it] == 0:
				arrDicByAp[x][it] = 1
				arrIdxIsread[it] = 1
				read += 1
		arrDicByAp[x].clear()
	else:
		arrIdxIsread[i] = -1
		while readByIdex < x:
			curentIdex += 1
			if arrIdxIsread[curentIdex] != -1:
				readByIdex += 1
			if arrIdxIsread[curentIdex] == 0:
				arrIdxIsread[curentIdex] = 1
				read += 1
				if curentIdex in arrDicByAp[arrInd[curentIdex]]:
					arrDicByAp[arrInd[curentIdex]][curentIdex] = 1
	print(Unread - read)


from sys import stdin
input = stdin.readline
(n, q) = 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)))


from sys import stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
(n, u) = map(int, input().split())
count = 0
q1 = [deque([]) for i in range(n + 1)]
vis = [0] * (u + 1)
q = deque([])
i = 0
r = 0
for _ in range(u):
	(t, x) = map(int, input().split())
	if t == 1:
		count += 1
		q.append((i, x))
		q1[x].append(i)
		i += 1
	elif t == 2:
		while q1[x]:
			index = q1[x].pop()
			if vis[index] == 0:
				vis[index] = 1
				count -= 1
	else:
		for y in range(r, x):
			(index, app) = q.popleft()
			if vis[index] == 0:
				vis[index] = 1
				count -= 1
				q1[app].popleft()
		if x > r:
			r = x
	print(count)


from __future__ import nested_scopes, generators, division, absolute_import, with_statement, print_function, unicode_literals
import sys, os, time
from collections import defaultdict

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if os.path.exists('test.txt'):
	sys.stdin = open('test.txt')

def solve():
	(n, q) = rv()
	events = rl(q)
	read = list()
	readidx = 0
	events_by_val = defaultdict(list)
	counter = 0
	res = list()
	for (event_type, val) in events:
		if event_type == 1:
			events_by_val[val].append(len(read))
			read.append(False)
			counter += 1
		elif event_type == 2:
			for idx in events_by_val[val]:
				if not read[idx]:
					read[idx] = True
					counter -= 1
			del events_by_val[val]
		else:
			while val > readidx:
				if not read[readidx]:
					read[readidx] = True
					counter -= 1
				readidx += 1
		res.append(counter)
	print('\n'.join(map(str, res)))
solve()


(n, q) = 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) = 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)
	ans.append(unread)
print('\n'.join(map(str, ans)))


from heapq import *
from collections import defaultdict, deque
total = 0
(N, Q) = map(int, input().split())
q = deque()
idx = 0
total = 0
A = [0] * N
B = [0] * N
ans = []
for _ in range(Q):
	(t, x) = map(int, input().split())
	x -= 1
	if t == 1:
		q.append(x)
		A[x] += 1
		B[x] += 1
		total += 1
	elif t == 2:
		total -= A[x]
		A[x] = 0
	else:
		while idx <= x:
			idx += 1
			y = q.popleft()
			B[y] -= 1
			if B[y] < A[y]:
				total -= 1
				A[y] = B[y]
	ans.append(str(total))
print('\n'.join(ans))


(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))


from collections import deque
(n, q) = map(int, input().split())
qu = deque()
first = [0] * (n + 1)
second = [0] * (n + 1)
total = 0
time = 0
ans = ''
for _ in range(q):
	(t, x) = map(int, input().split())
	if t == 1:
		first[x] += 1
		second[x] += 1
		total += 1
		qu.append(x)
	elif t == 2:
		total -= first[x]
		first[x] = 0
	else:
		while time < x:
			time += 1
			y = qu.popleft()
			second[y] -= 1
			if second[y] < first[y]:
				first[y] -= 1
				total -= 1
	ans += str(total) + '\n'
print(ans)


from sys import stdin
from collections import defaultdict
test = stdin.readlines()
(n, q) = map(int, test[0].split())
timeline = []
unread = defaultdict(lambda : [0, 0])
ans = 0
start = 0
out = []
for i in range(1, q + 1):
	(category, val) = map(int, test[i].split())
	if category == 1:
		timeline.append(val)
		unread[val][0] += 1
		ans += 1
	elif category == 2:
		ans -= unread[val][0]
		unread[val] = [0, len(timeline)]
	else:
		for j in range(start, val):
			app = timeline[j]
			if j >= unread[app][1]:
				unread[app][0] -= 1
				ans -= 1
		start = max(start, val)
	out.append(ans)
print('\n'.join(map(str, out)))


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] = []
	elif 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)


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)))


import random, math, sys
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter, OrderedDict
input = sys.stdin.readline

def solution(n, quer):
	total_cell = [0] * n
	max_2 = [0] * n
	max_3 = 0
	message = []
	total = 0
	time = 0
	ans = ''
	for i in quer:
		(t, x_t) = (i[0], i[1])
		if t == 1:
			total_cell[x_t - 1] += 1
			message.append(x_t)
			total += 1
		elif t == 2:
			total -= total_cell[x_t - 1]
			total_cell[x_t - 1] = 0
			max_2[x_t - 1] = len(message)
		else:
			for j in range(max_3, x_t):
				if j >= max_2[message[j] - 1]:
					total_cell[message[j] - 1] -= 1
					total -= 1
			max_3 = max(max_3, x_t)
		ans += str(total) + '\n'
	print(ans)

def input_test():
	(n, q) = map(int, input().strip().split(' '))
	quer = []
	for i in range(q):
		li = list(map(int, input().strip().split(' ')))
		li.append(True)
		quer.append(li)
	out = solution(n, quer)

def test():
	pass
input_test()


(n, p) = map(int, input().split())
L = []
A = [[] for _ in range(n)]
op = 0
bec = 0
rt = []
for i in range(p):
	(a, b) = map(int, input().split())
	if a == 2:
		while len(A[b - 1]) > 0:
			y = A[b - 1].pop()
			bec = bec - L[y]
			L[y] = 0
	elif a == 1:
		L.append(1)
		A[b - 1].append(len(L) - 1)
		bec += 1
	else:
		while b > op:
			bec = bec - L[op]
			L[op] = 0
			op += 1
	rt.append(str(bec))
print('\n'.join(rt))


from collections import defaultdict
(n, q) = map(int, input().split())
timeline = []
unread = defaultdict(lambda : [0, 0])
ans = 0
start = 0
out = []
for _ in range(q):
	(category, val) = map(int, input().split())
	if category == 1:
		timeline.append(val)
		unread[val][0] += 1
		ans += 1
	elif category == 2:
		ans -= unread[val][0]
		unread[val] = [0, len(timeline)]
	else:
		for i in range(start, val):
			app = timeline[i]
			if i >= unread[app][1]:
				unread[app][0] -= 1
				ans -= 1
		start = max(start, val)
	out.append(ans)
print('\n'.join(map(str, out)))


[n, q] = list(map(int, input().split(' ')))
total_cell = [0] * n
max_2 = [0] * n
max_3 = 0
message = []
total = 0
time = 0
ans = ''
for i in range(q):
	[t, x_t] = list(map(int, input().split(' ')))
	if t == 1:
		total_cell[x_t - 1] += 1
		message.append(x_t)
		total += 1
	elif t == 2:
		total -= total_cell[x_t - 1]
		total_cell[x_t - 1] = 0
		max_2[x_t - 1] = len(message)
	else:
		for j in range(max_3, x_t):
			if j >= max_2[message[j] - 1]:
				total_cell[message[j] - 1] -= 1
				total -= 1
		max_3 = max(max_3, x_t)
	ans += str(total) + '\n'
print(ans)


import collections
(n, q) = map(int, input().split())
Q = collections.deque()
A = [0] * n
B = A[:]
L = []
s = n = 0
for k in range(q):
	(type1, x) = 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())
ans = 0
res = ''
num = 0
pre = 0
noti = []
arr = [[0] * (n + 10) for i in range(2)]
for i in range(q):
	(op, x) = map(int, input().split())
	if op == 1:
		arr[0][x] += 1
		ans += 1
		num += 1
		noti += [x]
	elif op == 2:
		ans -= arr[0][x]
		arr[0][x] = 0
		arr[1][x] = num
	else:
		for j in range(pre, x):
			if j + 1 > arr[1][noti[j]]:
				ans -= 1
				arr[0][noti[j]] -= 1
		pre = max(pre, x)
	res += str(ans) + '\n'
print(res)