// 私は猫です

#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_64 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){ 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; return u; }
inline int merge(int u,int v){
	if(!u||!v)return u^v;
	if(h[u]<h[v])return rs[u]=merge(rs[u],v),pushup(u);
	return ls[v]=merge(u,ls[v]),pushup(v);
}
pii split(int u,int k){
	if(!u)return mkp(0,0);
	if(k<=siz[ls[u]]){
		auto [x,y]=split(ls[u],k);
		return ls[u]=y,mkp(x,pushup(u));
	}
	auto [x,y]=split(rs[u],k-siz[ls[u]]-1);
	return rs[u]=x,mkp(pushup(u),y);
}
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,x,y; cin>>i>>y,++i,++y,x=q[i],q[i]=y;
			st[x].erase(i),st[y].insert(i);
			const int l=rnk(i),r=rnk(i+n);
			auto [A,B]=split(R,l-1); auto [C,D]=split(B,r-l+1);
			R=merge(A,D);
			auto it=st[y].upper_bound(i);
			if(it!=st[y].end())insert(B,rnk(n+(*it)));
			else insert(B,rnk(y));
		}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();
}