// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=600005;
mt19937 eng(time(0));
int siz[maxn],num[maxn],q[maxn],fa[maxn],ls[maxn],rs[maxn],n,R,testid;
ull h[maxn];
set<int>st[maxn];
inline void remake(int u){ siz[u]=1,num[u]=(u<=n),h[u]=eng(),ls[u]=rs[u]=fa[u]=0; }
inline int pushup(int u){ return siz[u]=siz[ls[u]]+siz[rs[u]]+1,num[u]=num[ls[u]]+num[rs[u]]+(u<=n),fa[ls[u]]=fa[rs[u]]=u,fa[u]=0,u; }
inline int merge(int x,int y){
	if(!x||!y)return x^y;
	if(h[x]<h[y])return rs[x]=merge(rs[x],y),pushup(x);
	return ls[y]=merge(x,ls[y]),pushup(y);
}
pii split(int u,int sz){
	if(!u)return make_pair(0,0);
	if(sz<=siz[ls[u]]){
		auto [a,b]=split(ls[u],sz);
		return ls[u]=b,make_pair(a,pushup(u));
	}
	auto [a,b]=split(rs[u],sz-siz[ls[u]]-1);
	return rs[u]=a,make_pair(pushup(u),b);
}
void insert(int u,int k){
	auto [x,y]=split(R,k);
	R=merge(x,merge(u,y));
}
int rnk(int u,int op=1){
	int r=(op|(u<=n))+(op?siz[ls[u]]:num[ls[u]]),lst=u;
	while(lst=u,u=fa[u])if(lst==rs[u])r+=(op|(u<=n))+(op?siz[ls[u]]:num[ls[u]]);
	return r;
}
void solve(){
	cin>>testid>>n,++n;
	F(i,1,n<<1)remake(i); R=merge(1,n+1);
	int c=1;
	F(_,1,n-1){
		int op; cin>>op;
		if(op==1){
			int x; cin>>x,++x,q[++c]=x;
			st[x].insert(c),insert(merge(c,c+n),rnk(x));
		}else if(op==2){
			int i,y,x; cin>>i>>y,++i,++y,x=q[i],q[i]=y;
			st[x].erase(i),st[y].insert(i);
			int l=rnk(i),r=rnk(i+n);
			auto [a,bc]=split(R,l-1);
			auto [b,c]=split(bc,r-l+1);
			R=merge(a,c);
			auto it=next(st[y].find(i));
			if(it==st[y].end())insert(b,rnk(y));
			else insert(b,rnk((*it)+n));
		}else{
			int x; cin>>x,++x,cout<<(rnk(x,0)-1)<<'\n';
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}