#include<bits/stdc++.h>
#define N 600005
#define ls tr[u].lss
#define rs tr[u].rss
using namespace std;
int sub,rt,n=1,q,p[N];
set<int> sns[N];
mt19937 rnd(114514);
struct node{int fa,pr,sz,szz,lss,rss;}tr[N];
void nnd(int u){tr[u]=(node){0,rnd(),1,u<=q,0,0};}
int pu(int u){
	return tr[u].sz=tr[ls].sz+tr[rs].sz+1,
	tr[u].szz=tr[ls].szz+tr[rs].szz+(u<=q),
	tr[ls].fa=u,tr[rs].fa=u,tr[u].fa=0,u;}
int mrg(int u,int v){
	if(!min(u,v))return u+v;
	if(tr[u].pr<tr[v].pr)return rs=mrg(rs,v),pu(u);
	return swap(u,v),ls=mrg(v,ls),pu(u);
}
pair<int,int> spt(int u,int sz){
	if(!u)return make_pair(0,0);
	if(sz<=tr[ls].sz){
		auto [a,b]=spt(ls,sz);
		return ls=b,make_pair(a,pu(u));
	}
	auto [a,b]=spt(rs,sz-tr[ls].sz-1);
	return rs=a,make_pair(pu(u),b);
}
void ist(int sz,int u){auto [a,b]=spt(rt,sz);rt=mrg(a,mrg(u,b));}
int rk(int u,int op=1){
	int r=(op|(u<=q))+(op?tr[ls].sz:tr[ls].szz),lst=u;
	while(lst=u,u=tr[u].fa)
		if(lst==rs)r+=(op|(u<=q))+(op?tr[ls].sz:tr[ls].szz);
	return r;
}
void solve(){
	cin>>sub>>q,++q;
	for(int i=1;i<=2*q;i++)nnd(i);
	rt=mrg(1,q+1);
	for(int op,i,x,y,z,qi=1;qi<q;qi++){
		cin>>op;
		if(op==1)cin>>x,++x,p[++n]=x,sns[x].insert(n),ist(rk(x),mrg(n,n+q));
		else if(op==2){
			cin>>i>>y,++i,++y,x=p[i],p[i]=y;
			sns[x].erase(i),sns[y].insert(i);
			int l=rk(i),r=rk(i+q);
			auto [a,bc]=spt(rt,l-1);
			auto [b,c]=spt(bc,r-l+1);
			rt=mrg(a,c);
			auto it=next(sns[y].find(i));
			if(it==sns[y].end())ist(rk(y),b);
			else ist(rk((*it)+q),b);
		}
		else cin>>z,++z,cout<<rk(z,0)-1<<'\n';
	}
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	solve();
	return 0;
}