LINK：树
考虑暴力 保存每个版本的父亲 然后暴力向上跳。得分20.
考虑离线 可以离线那么就可以先把树给搞出来 然后考虑求k级祖先 可以倍增求。
如何判断合法 其实要求路径上的边的时间戳<=当前时间戳 这个也可以倍增做。
当然我脑抽了 把询问版本排序后利用并查集判连通性了。
考虑正解：这下就有两个方向了：
一个是倍增数组的问题 容易想到如果倍增数组可以求出 那么问题迎刃而解 倍增数组每个位置最多被更新一次 所以每次暴力判断是否可以更新 递归来做这个事情。
复杂度不太能证明。
还有一个是 如果可以直接求出k级祖先利用可持久化并查集也可以求出答案。
那么这个k级祖先可以利用LCT来求 access之后暴力在splay上跳。可持久化并查集判定。
第二个询问可以二分一下 然后定位 然后判定。复杂度nlog^2.
这个做法非常不优美。
还是考虑 将判定条件转到 路径上的边的出现时间<当前时间来判断。
LCT维护子树内的最大值 就可以直接在LCT上跳了。
k级祖先也是如此 可以直接跳也可以求出来那部分点再跳。
const int MAXN=100010;
int n,m,T,last,len,now;
int c[MAXN][2],f[MAXN],fa[MAXN],mx[MAXN],sz[MAXN],rev[MAXN],v[MAXN];
inline bool pd(int x){return c[f[x]][0]==x||c[f[x]][1]==x;}
IV pushup(int x)
{
sz[x]=sz[l(x)]+sz[r(x)]+1;
mx[x]=max(v[x],max(mx[l(x)],mx[r(x)]));
}
IV rotate(int x)
{
int old=f[x],oldf=f[old],k=c[old][1]==x;
c[old][k]=c[x][k^1];c[x][k^1]=old;
if(pd(old))c[oldf][c[oldf][1]==old]=x;
if(c[old][k])f[c[old][k]]=old;
f[old]=x;f[x]=oldf;pushup(old);
}
IV splay(int x)
{
while(pd(x))
{
int old=f[x];
if(pd(old))rotate(((c[old][1]==x)^(c[f[old]][1]==old))?x:old);
rotate(x);
}
pushup(x);
}
IV access(int x)
{
for(int y=0;x;x=f[y=x])
splay(x),c[x][1]=y,pushup(x);
}
IV LINK(int x,int y)//这里题目中保证了x没有父亲.
{
access(x);
splay(x);
v[x]=now;
fa[x]=f[x]=y;
pushup(x);
}
inline int get_mx(int x,int b)
{
if(mx[x]<=b)return 0;
while(x)
{
if(r(x)&&mx[r(x)]>b)x=r(x);
else
{
if(v[x]>b)return x;
else x=c[x][0];
}
}
return x;
}
inline int get_Kth(int b,int x,int k)
{
access(x);
splay(x);
int w=get_mx(x,b);
access(fa[w]);
splay(x);
++k;
if(sz[x]<k)return 0;
while(x)
{
if(sz[r(x)]>=k)x=r(x);
else
{
if(sz[r(x)]+1==k)return x;
k=k-sz[r(x)]-1;
x=l(x);
}
}
return x;
}
inline int get_dep(int b,int x)
{
access(x);
splay(x);
int w=get_mx(x,b);
access(fa[w]);
splay(x);
return sz[x]-1;
}
int main()
{
freopen("1.in","r",stdin);
//freopen("tree.out","w",stdout);
get(n);get(m);get(T);
rep(1,m,i)
{
int get(op),u,v,b;now=i;
op=(op+T*last)%3;
if(!op)
{
get(u);get(v);
u=(u+T*last)%n+1;
v=(v+T*last)%n+1;
LINK(u,v);
}
if(op==1)
{
get(b);get(u);int get(k);
b=(b+T*last)%m;
u=(u+T*last)%n+1;
k=(k+T*last)%n;
put(last=get_Kth(b,u,k));
}
if(op==2)
{
get(b);get(u);
b=(b+T*last)%m;
u=(u+T*last)%n+1;
put(last=get_dep(b,u));
}
}
return 0;
}