前置技能：可持久化数组，并查集

考虑并查集的fa数组能够表示这个并查集。所以我们只需要按照可持久化数组的套路维护fa数组即可。
但众所周知，没有优化的并查集时间复杂度是每次最坏$O(n)$，妥妥TLE&MLE。
考虑最常规优化：路径压缩。每一次找到根节点后把其所有祖先和自己的父亲都指向根。普通的路径压缩并查集时间复杂度为均摊$O(logn)$.但在可持久化并查集中，这存在两个问题：

• 每次修改至多$O(logn)$个祖先，且在可持久化数组中修改一个元素的时空代价是$O(logn)$，即总空间复杂度为$O(mlog^2n)$,会MLE。
• 路径压缩并查集的时间复杂度是均摊的，可能存在某次操作的时间复杂度是$O(n)$.可以构造数据，多次访问需要$O(n)$进行路径压缩的版本，即可让他达到最坏空间复杂度$O(mnlogn)$,更是MLE飞。

另一种优化：按秩合并。即按树高合并，在维护fa同时维护dep,表示以这个点所在集合的最大深度。合并时将深度小的集合合并到深度大的集合上，使最大深度不增加（如果两个集合深度相同，合并后要更新深度）。可以证明按秩合并并查集的时间复杂度为每次$O(logn)$.
因此每次访问至多$O(logn)$个点，至多修改2个点，因此时间复杂度$O(mlog^2n)$,空间复杂度$O(mlogn)$

typedef int ll;
/**********/省略快读
#define MAXN 200011
ll n,m;
struct Lasting_Segment_Tree
{
    struct node
    {
        ll lson,rson;
        ll fa,dep;//父亲，深度
    }t[MAXN<<5|1];
    ll cnt;
    Lasting_Segment_Tree()
    {
        cnt=0;
    }
    #define rt t[num]
    void build(ll& num,un l=1,un r=n)//建树
    {
        num=++cnt;
        if(l==r)rt.fa=l,rt.dep=1;
        else
        {
            un mid=(l+r)>>1;
            build(rt.lson,l,mid);
            build(rt.rson,mid+1,r);
        }
    }
    void modify(ll& num,ll pre,un pos,ll fa,un l=1,un r=n)//现在节点是num，前一个版本的现在节点是pre，要将pos位置的fa改为fa
    {
        num=++cnt;//新建节点
        rt=t[pre];
        if(l==r)//走到了
        {
            rt.fa=fa;
            return;
        }
        un mid=(l+r)>>1;
        if(pos<=mid)modify(rt.lson,t[pre].lson,pos,fa,l,mid);
        else modify(rt.rson,t[pre].rson,pos,fa,mid+1,r);
    }
    void add(ll num,un pos,un l=1,un r=n)//现在节点是num,要讲pos位置深度+1
    {
        if(l==r)
        {
            ++rt.dep;
            return;
        }
        un mid=(l+r)>>1;
        if(pos<=mid)add(rt.lson,pos,l,mid);
        else add(rt.rson,pos,mid+1,r);
    }
    pll Query(ll num,un pos,un l=1,un r=n)//返回pos位置的fa和dep
    {
        if(l==r)return pll(rt.fa,rt.dep);
        un mid=(l+r)>>1;
        if(pos<=mid)return Query(rt.lson,pos,l,mid);
        else return Query(rt.rson,pos,mid+1,r);
    }
}sgt;
ll root[MAXN];//每个版本的根节点
pll find(ll w,ll x)//找第w个版本下x的根和深度
{
    pll tmp=sgt.Query(root[w],x);
    if(tmp.first==x)return tmp;
    return find(w,tmp.first);//不能路径压缩!
}
int main()
{
    n=read(),m=read();
    ll lastans=0;
    sgt.build(root[0]);
    for(ll i=1;i<=m;++i)
    {
        ll op=read();
        root[i]=root[i-1];//复制
        if(op==1)
        {
            pll x,y;
            x=find(i,read()^lastans);
            y=find(i,read()^lastans);
            if(x.first==y.first)continue;
            if(x.second>y.second)std::swap(x,y);
            sgt.modify(root[i],root[i-1],x.first,y.first);//深度小的合并到深度大的集合
            if(x.second==y.second)sgt.add(root[i],y.first);//深度相同要深度+1
        }
        else if(op==2)root[i]=root[read()^lastans];
        else
        {
            ll x=read()^lastans,y=read()^lastans;
            lastans=(find(i,x).first==find(i,y).first);
            printf("%d\n",lastans);
        }
    }
    return 0;
}