#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+114;
//2*i-1 father to u 2*i u to father
struct node{
    int l,r;//l:) r:(
    node(int L=0,int R=0){
        l=L,r=R;
    }
    node operator+(const node&x)const{
        node res=node();
        res=x;
        int del=min(r,x.l);
        res=node(l+x.l-del,r+x.r-del);
        return res;
    }
};
node tr[maxn];
int ls[maxn],rs[maxn],rk[maxn];
int fa[maxn];
int sz[maxn];
mt19937 rd(11245141);
set<int> E[maxn];
int root;
int q,tot;
void pushup(int cur){
    tr[cur]=node((cur%2)^1,cur%2);
    sz[cur]=1;
    if(ls[cur]!=0) tr[cur]=tr[ls[cur]]+tr[cur],sz[cur]+=sz[ls[cur]];
    if(rs[cur]!=0) tr[cur]=tr[cur]+tr[rs[cur]],sz[cur]+=sz[rs[cur]];
}
int merge(int u,int v){
    if(u==0||v==0) return u+v;
    if(rk[u]>rk[v]){
        rs[u]=merge(rs[u],v);
        fa[rs[u]]=u;
        pushup(u);
        return u;
    }else{
        ls[v]=merge(u,ls[v]);
        fa[ls[v]]=v;
        pushup(v);
        return v;
    }
}
void split(int cur,int k,int &l,int &r){
    if(cur==0){
        l=r=0;
        return ;
    }
    if(sz[ls[cur]]+1<=k){
        l=cur;
        fa[rs[l]]=0;
        split(rs[l],k-sz[ls[cur]]-1,rs[l],r);
        fa[rs[l]]=l;
        pushup(l);
    }else{
        r=cur;
        fa[ls[r]]=0;
        split(ls[r],k,l,ls[r]);
        fa[ls[r]]=r;
        pushup(r);
    }
}
int query(int cur){
    int ans=sz[ls[cur]];
    while(fa[cur]!=0){
        if(cur==rs[fa[cur]]) ans+=sz[ls[fa[cur]]]+1;
        cur=fa[cur];
    }
    return ans;
}
int siz(int u){
    //cout<<"siz"<<u<<' '<<(query(2*u)-query(2*u-1)-1)/2<<'\n';
    return (query(2*u)-query(2*u-1)-1)/2;
}
void ins(int u,int v,int w){
    if(E[u].lower_bound(v)==E[u].end()){
        int x=0,y=0;
        split(root,query(u*2),x,y);
        root=merge(x,merge(w,y));
    }else{
        int x=0,y=0;
        int nxt=(*E[u].lower_bound(v));
        split(root,query(nxt*2-1),x,y);
        root=merge(x,merge(w,y));
    }
    E[u].insert(v);
}
int del(int u,int v){
    //cout<<"Cut"<<u<<" "<<v<<'\n';
    int x=0,y=0,z=0;
    split(root,query(2*v-1),x,y);
    split(y,query(2*v)+1,y,z);
    root=merge(x,z);
    E[u].erase(v);
    return y;
}
int ask(int cur){
    int sum=query(cur);
    node res=tr[ls[cur]];
    while(fa[cur]!=0){
        if(cur==rs[fa[cur]]){
            res=(tr[ls[fa[cur]]]+(fa[cur]%2==1?node(0,1):node(1,0)))+res;
        }
        cur=fa[cur];
    }
    return (sum-res.l-res.r)/2;
}
void dfs(int u){
    if(u==0) return ;
    dfs(ls[u]);
    cout<<u<<' '<<ls[u]<<' '<<rs[u]<<' '<<tr[u].l<<' '<<tr[u].r<<'\n';
    dfs(rs[u]);
}
int link[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    tot++;
    tr[1]=node(0,1);
    tr[2]=node(1,0);
    rk[1]=rd(),rk[2]=rd();
    sz[1]=sz[2]=1;
    root=merge(1,2);
    int c;
    cin>>c>>q;
    while(q--){
        int opt;
        cin>>opt;
        if(opt==1){
            int lst;
            cin>>lst;
            lst++;
            tot++;
            link[tot]=lst;
            tr[tot*2-1]=node(0,1),tr[tot*2]=node(1,0);
            rk[tot*2-1]=rd(),rk[tot*2]=rd();
            sz[tot*2-1]=sz[tot*2]=1;
            int w=merge(tot*2-1,tot*2);
            ins(lst,tot,w);
        }else if(opt==2){
            int x,y;
            cin>>x>>y;
            x++,y++;
            //cout<<"Cut"<<link[x]<<' '<<x<<'\n';
            int w=del(link[x],x);
            //cout<<"Del"<<w<<' '<<sz[w]<<'\n';
            ins(y,x,w);
            link[x]=y;
        }else{
            int z;
            cin>>z;
            z++;
            cout<<(tot-ask(z*2-1)-siz(z))-1<<'\n';
        }
        //dfs(root);
        //cout<<"------------------\n";
    }
    return 0;
}