膜拜神犇出题人管理员！！膜拜yler和ZSY！！
没错yler连续教我这个蒟蒻写起床困难综合症和睡觉困难综合症%%%Orz，所以按位贪心的思路可以继承下来
这里最好还是写树剖吧，不过我根本不会，于是只好来个LCT，用unsigned long long维护链上双向的按位操作。具体方法yler已经讲得很好啦
注意因为信息的维护是有方向性的，所以pushdown要写规范。。。。。。
#include<cstdio>
#define RG register
#define R RG int
#define I inline void
#define TP template<typename T>
#define lc c[x][0]
#define rc c[x][1]
#define G ch=getchar()
#define upd switch(y){\
case 1:v[x]=(B){_0,z};break;\
case 2:v[x]=(B){z,_I};break;\
case 3:v[x]=(B){z,~z};\
}
typedef unsigned long long L;
const L _0=0ull,_1=1ull,_I=~_0;
const int N=100009;
struct B{
L f0,f1;
I merge(RG B x,RG B y){
f0=(~x.f0&y.f0)|(x.f0&y.f1);
f1=(~x.f1&y.f0)|(x.f1&y.f1);
}
}v[N],b[N],e[N];
bool r[N];
int f[N],c[N][2];
TP I swap(RG T&x,RG T&y){
RG T z=x;x=y;y=z;
}
TP I in(RG T&x){
RG char G;
while(ch<'-')G;
x=ch&15;G;
while(ch>'-')x*=10,x+=ch&15,G;
}
inline bool nroot(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I up(R x){//之前试着写数组发现WA了，原因是本来需要继续运算的信息又被覆盖掉，用结构体弄一下就好了
b[x]=e[x]=v[x];
if(lc)b[x].merge(b[lc],b[x]),e[x].merge(e[x],e[lc]);
if(rc)b[x].merge(b[x],b[rc]),e[x].merge(e[rc],e[x]);
}
I rev(R x){
swap(b[x],e[x]);swap(lc,rc);r[x]^=1;
}
I down(R x){
if(r[x])rev(lc),rev(rc),r[x]=0;
}
I all(R x){
if(nroot(x))all(f[x]);down(x);
}
I rot(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
up(f[w]=y);f[y]=x;f[x]=z;
}
I splay(R x){
all(x);R y;
while(nroot(x)){
if(nroot(y=f[x]))
rot((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
rot(x);
}
up(x);
}
I access(R x){
for(R y=0;x;y=x,x=f[x])
splay(x),rc=y,up(x);
}
I mroot(R x){
access(x);splay(x);rev(x);
}
int main(){
R n,m,k,q,x,y;
RG L i,z,g0,g1,w,ans;
in(n);in(m);in(k);--k;
for(x=1;x<=n;++x){
in(y);in(z);upd;up(x);
}
for(i=1;i<n;++i){
in(x);in(y);
mroot(x);f[x]=y;
}
while(m--){
in(q);in(x);in(y);in(z);
if(q&1){
mroot(x);access(y);splay(y);
g0=b[y].f0;g1=b[y].f1;w=ans=_0;
for(i=_1<<k;i;i>>=1)//和起床困难综合症一样贪心下去
if(g0&i)ans|=i;
else if((g1&i)&&(w|i)<=z)ans|=i,w|=i;
printf("%llu\n",ans);
}
else{upd;splay(x);}
}
return 0;
}