# include <bits/stdc++.h>

const int N=300010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

std::mt19937 rng(114514);

struct Node{
	int val,lc,rc,rnd,siz,fa,mx;
}tr[N];
int cnt;

inline int& lc(int x){
	return tr[x].lc;
}
inline int& rc(int x){
	return tr[x].rc;
}
inline void node(int &x,int val){
	return x=++cnt,tr[x]=(Node){val,0,0,(int)rng(),1,0,val},void();
}

inline void psup(int x){
	tr[x].siz=tr[lc(x)].siz+tr[rc(x)].siz+1;
	tr[x].mx=std::min({tr[lc(x)].mx,tr[rc(x)].mx,tr[x].val});
	if(lc(x)) tr[lc(x)].fa=x;
	if(rc(x)) tr[rc(x)].fa=x;
	return;
}

void merge(int &cur,int u,int v){
	if(!u||!v) return cur=u|v,void();
	tr[u].fa=tr[v].fa=0; // ???
	if(tr[u].rnd<tr[v].rnd) cur=u,merge(rc(cur),rc(u),v);
	else cur=v,merge(lc(cur),u,lc(v));
	psup(cur);
	return;
}
void split(int cur,int &u,int &v,int k){
	if(!cur) return u=v=0,void();
	tr[cur].fa=0;
	if(tr[lc(cur)].siz+1<=k) u=cur,split(rc(cur),rc(u),v,k-tr[lc(cur)].siz-1),psup(u);
	else v=cur,split(lc(cur),u,lc(v),k),psup(v);
	return;
}
inline int getrk(int x){
	int ans=1+tr[lc(x)].siz;
	while(tr[x].fa) ans+=(tr[lc(tr[x].fa)].siz+1)*(x!=lc(tr[x].fa)),x=tr[x].fa;
	return ans;
}
void splitv(int cur,int &u,int &v,int k){
	if(!cur) return u=v=0,void();
	tr[cur].fa=0;
	if(std::min(tr[lc(cur)].mx,tr[cur].val)>=k) u=cur,split(rc(cur),rc(u),v,k),psup(u);
	else v=cur,splitv(lc(cur),u,lc(v),k),psup(v);
}

int n,T,rt; 
// idx x -> x+1

int main(void){
	T=read(),n=read(),node(rt,1); // cnt = 1
	while(n--){
		int op=read();
		if(op==1){
			int x=read(),y; node(y,cnt+1);
			if(x==0){
				merge(rt,y,rt);
			}else{
				++x;
				int k=getrk(x);
				int a,b; split(rt,a,b,k-1); merge(a,a,y); merge(rt,a,b);
			}
		}else if(op==2){
//			int y=read()+1,x=read();
//			int k=getrk(x);
//			int a,b,c; split(rt,k,a,b); splitv(b,b,c,t);
		}else{
			int y=read()+1;
			printf("%d\n",getrk(y));
		}
		
//		for(int i=1;i<=cnt;++i){
//			printf("rk = %d fa = %d size = %d lc = %d rc = %d\n",getrk(i),tr[i].fa,tr[i].siz,tr[i].lc,tr[i].rc);
//		}
	}
	 
	
	return 0;
}