link

#include <bits/stdc++.h>
#define DISABLE_MMAP
#pragma terget("avx,avx2,avx256f,sse2,sse3,sse4,sse4.2")
#define int unsigned long long
using namespace std;

const int N = 5e5;
int n, m, k, bit[N], a[N], from[N];
int deep[N], siz[N], bigson[N], fa[N], up[N], dfn[N], dfncnt;
vector<int> g[N];

struct point{
	int r0, r1, l0, l1;
	void make(int a, int b, int c, int d){
		r0 = a, r1 = b, l0 = c, l1 = d;
		return ;
	}
	point operator + (const point &b){
		point res;
		res.r0 = (~r0 & b.r0) | (r0 & b.r1);
		res.r1 = (~r1 & b.r0) | (r1 & b.r1);
		res.l0 = (~b.l0 & l0) | (b.l0 & l1);
		res.l1 = (~b.l1 & l0) | (b.l1 & l1);
		return res;
	}
}val[N];
vector<point> vecl, vecr;

void decomp(int u, int pre){
	deep[u] = deep[pre] + 1, siz[u] = 1; bigson[u] = 0, fa[u] = pre;
	for(int v : g[u]){
		if(v == pre) continue;
		decomp(v, u); siz[u] += siz[v];
		if(siz[v] > siz[bigson[u]]) bigson[u] = v;
	}
	return ;
}
void calup(int u, int pre, int val){
	dfn[u] = ++dfncnt, from[dfncnt] = u;
	up[u] = val; if(bigson[u]) calup(bigson[u], u, val);
	for(int v : g[u]){
		if(v == pre || v == bigson[u]) continue;
		calup(v, u, v);
	}
	return ;
}

void Build(int u, int l, int r){
	if(l == r){
		int all = (0ull - 1ull); l = from[l];
		if(bit[l] == 1) val[u].make(0 & a[l], all & a[l], 0 & a[l], all & a[l]);
		if(bit[l] == 2) val[u].make(0 | a[l], all | a[l], 0 | a[l], all | a[l]);
		if(bit[l] == 3) val[u].make(0 ^ a[l], all ^ a[l], 0 ^ a[l], all ^ a[l]);
		return ;
	}
	int mid = (l + r) >> 1ull;
	Build(2 * u, l, mid);
	Build(2 * u + 1, mid + 1, r);
	val[u] = val[2 * u] + val[2 * u + 1];
	return ;
}

void Modify(int u, int l, int r, int x){
	if(l == r){
		int all = (0ull - 1ull); l = from[l];
``		if(bit[l] == 2) val[u].make(0 | a[l], all | a[l], 0 | a[l], all | a[l]);
		if(bit[l] == 3) val[u].make(0 ^ a[l], all ^ a[l], 0 ^ a[l], all ^ a[l]);
		return ;
	}
	int mid = (l + r) >> 1ull;
	if(x <= mid) Modify(2 * u, l, mid, x);
	if(mid < x) Modify(2 * u + 1, mid + 1, r, x);
	val[u] = val[2 * u] + val[2 * u + 1];
	return ;
}

point Query(int u, int l, int r, int L, int R){
	if(L <= l && r <= R)
		return val[u];
	int mid = (l + r) >> 1ull;
	if(R <= mid) return Query(2 * u, l, mid, L, R);
	if(mid < L) return Query(2 * u + 1, mid + 1, r, L, R);
	return Query(2 * u, l, mid, L, R) + Query(2 * u + 1, mid + 1, r, L, R);
}

point lca(int x, int y){
	vecl.clear(), vecr.clear();
	// 先倍增往上跳喵，直接套板子喵
	while(up[x] != up[y]){
		if(deep[up[x]] <= deep[up[y]])
			vecr.push_back(Query(1, 1, n, dfn[up[y]], dfn[y])), y = fa[up[y]];
		else{
			point tmp = Query(1, 1, n, dfn[up[x]], dfn[x]);
			tmp.make(tmp.l0, tmp.l1, tmp.r0, tmp.r1);
			vecl.push_back(tmp), x = fa[up[x]];
		}
	}
	if(deep[x] <= deep[y]) vecr.push_back(Query(1, 1, n, dfn[x], dfn[y]));
	if(deep[x] > deep[y]){
		point tmp = Query(1, 1, n, dfn[y], dfn[x]);
		tmp.make(tmp.l0, tmp.l1, tmp.r0, tmp.r1);
		vecl.push_back(tmp);
	}
	point res;
	if(!vecl.empty() && vecr.empty()){
		res = vecl[0];
		if(vecl.size() >= 2)
			for(long long i = 1; i < vecl.size(); i++) res = res + vecl[i];
		return res;
	}
	else if(vecl.empty() && !vecr.empty()){
		res = vecr[vecr.size() - 1];
		if(vecr.size() >= 2)
			for(long long i = vecr.size() - 2; i >= 0; i--) res = res + vecr[i];
		return res;
	}
	res = vecl[0];
	if(vecl.size() >= 2)
		for(long long i = 1; i < vecl.size(); i++) res = res + vecl[i];
	if(vecr.size() >= 2)
		for(long long i = vecr.size() - 2; i >= 0; i--) res = res + vecr[i];
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	for(long long i = 1; i <= n; i++) cin >> bit[i] >> a[i];
	for(long long i = 1; i < n; i++){
		int x, y; cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	decomp(1, 0);
	calup(1, 0, 1);
	
	Build(1, 1, n);
	
	while(m--){
		int op, x, y, z;
		cin >> op >> x >> y >> z;
		if(op == 1){
			// 还要一个数位 DP 喵。
			int res = 0;
			point S = lca(x, y);
			int now0, now1;
			for(long long i = k - 1; i >= 0; i--){
				now0 = 1ull & (S.r0 >> i);
				now1 = 1ull & (S.r1 >> i);
				if(now0 >= now1 || (1ull << i) > z) res |= now0 * (1ull << i);
				else res |= now1 * (1ull << i), z -= (1ull << i);
			}
			cout << res << endl;
		}
		if(op == 2){
			bit[x] = y, a[x] = z;
			Modify(1, 1, n, dfn[x]);
		}
	}
	return 0;
}