#include <bits/stdc++.h>

namespace Initial {
	#define ll int
	#define ull unsigned long long
	#define fi first
	#define se second
	#define mkp make_pair
	#define pir pair <int, int>
	#define pb push_back
	#define i128 __int128
	using namespace std;
	const ll maxn = 6e5 + 10, inf = 1e9, mod = 1e9 + 7;
	ll power(ll a, ll b = mod - 2) {
		ll s = 1;
		while(b) {
			if(b & 1) s = 1ll * s * a %mod;
			a = 1ll * a * a %mod, b >>= 1;
		} return s;
	}
	template <class T>
	const inline ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
	template <class T>
	const inline void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
	template <class T>
	const inline void chkmax(T &x, const T y) { x = x < y? y : x; }
	template <class T>
	const inline void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;

namespace Read {
	char buf[1 << 22], *p1, *p2;
//	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
	template <class T>
	const inline void rd(T &x) {
		char ch; bool neg = 0;
		while(!isdigit(ch = getchar()))
			if(ch == '-') neg = 1;
		x = ch - '0';
		while(isdigit(ch = getchar()))
			x = (x << 1) + (x << 3) + ch - '0';
		if(neg) x = -x;
	}
} using Read::rd;

ll n, m; set <ll> st[maxn];
mt19937 rnd(20090623);

struct Treap {
	ll fa[maxn], siz[maxn], lc[maxn], rc[maxn], dnr[maxn];
	ll val[maxn], cnt[maxn];
	void pushup(ll p) {
		siz[p] = siz[lc[p]] + siz[rc[p]] + 1;
		cnt[p] = cnt[lc[p]] + cnt[rc[p]] + val[p];
	}
	ll merge(ll p, ll q) {
		fa[p] = fa[q] = 0;
		if(!p || !q) return p | q;
		if(dnr[p] < dnr[q])
			return pushup(fa[rc[p] = merge(rc[p], q)] = p), p;
		else
			return pushup(fa[lc[q] = merge(p, lc[q])] = q), q;
	}
	void split(ll p, ll k, ll &x, ll &y) {
		if(!p) return x = y = 0, void();
		fa[p] = 0;
		if(siz[lc[p]] + 1 <= k) {
			split(rc[p], k - 1 - siz[lc[p]], rc[p], y);
			return fa[rc[p]] = p, pushup(x = p);
		} else {
			split(lc[p], k, x, lc[p]);
			return fa[lc[p]] = p, pushup(y = p);
		}
	}
	ll getrk(ll p) {
		ll s = siz[lc[p]] + 1;
		for(ll q = p; p = fa[p]; q = p)
			if(rc[p] == q) s += siz[lc[p]] + 1;
		return s;
	}
	ll qry(ll p) {
		ll s = cnt[lc[p]] + val[p];
		for(ll q = p; p = fa[p]; q = p)
			if(rc[p] == q) s += cnt[lc[p]] + val[p];
		return s;
	}
	void Newnode(ll p, ll w) {
		siz[p] = 1, dnr[p] = rnd(), cnt[p] = val[p] = w;
	} 
} tr; ll rt, f[maxn];

signed main() {
	rd(n), rd(n); st[0].insert(inf);
	while(n--) {
		ll op, x; rd(op), rd(x);
		if(op == 1) {
			st[x].insert(++m), f[m] = x, st[m].insert(inf);
			tr.Newnode(2 * m, 0), tr.Newnode(2 * m - 1, 1);
			ll k = x? tr.getrk(2 * x - 1) : 0;
			ll s1, s2; tr.split(rt, k, s1, s2);
			rt = tr.merge(tr.merge(s1, tr.merge(2 * m - 1, 2 * m)), s2);
		} else if(op == 2) {
			ll y; rd(y);
			ll k1 = tr.getrk(2 * x - 1), k2 = tr.getrk(2 * x);
			ll s1, sx, s2; tr.split(rt, k2, s1, s2);
			tr.split(s1, k1 - 1, s1, sx);
			rt = tr.merge(s1, s2);
			ll z = *st[y].upper_bound(x);
			ll k = y? tr.getrk(z == inf? 2 * y - 1 : 2 * z) : 0;
			tr.split(rt, k, s1, s2);
			rt = tr.merge(tr.merge(s1, sx), s2);
			st[f[x]].erase(x), st[f[x] = y].insert(x);
		} else {
			printf("%d\n", tr.qry(2 * x - 1));
		}
	}
	return 0;
}