样例第二个过不去/kk

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

int read() {
	int f = 1, s = 0; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48);
	return s * f;
}

const int N = 100010, M = N << 1;
const long long INF = 1 << 30;

int h[N], e[M], ne[M], idx;
int n, m, w[N], nw[N], top[N];
int son[N], sz[N], id[N], cnt;
int fa[N], dep[N];

struct node {
	node *s[2]; int maxid;
	node() { s[0] = s[1] = NULL; maxid = 0; }
}*root[N];
void add(int a, int b) {
	e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

// ------------ tree cut ----------------
void dfs1(int u, int father, int depth) {
	dep[u] = depth, fa[u] = father, sz[u] = 1;
	for (int i = h[u]; i; i = ne[i]) {
		int j = e[i];
		if (j == father) continue;
		dfs1(j, u, depth + 1);
		sz[u] += sz[j];
		if (sz[son[u]] < sz[j]) son[u] = j;
	}
}
void dfs2(int u, int t) {
	top[u] = t, id[u] = ++ cnt, nw[cnt] = w[u];
	if (son[u]) dfs2(son[u], t);
	
	for (int i = h[u]; i; i = ne[i]) {
		int j = e[i];
		if (j == fa[u] || j == son[u]) continue;
		dfs2(j, j);
	}
}

// ------------- 01trie ---------------

void build() {
	node *u = root[0] = new node();
	dep(i, 30, 0) u -> s[0] = new node(), u = u -> s[0];
}
void insert(int x) {
	node *u = root[x] = new node(), *p = root[x - 1];
	int v = nw[x];
	dep(i, 30, 0) {
		if (p) *u = *p;
		u -> maxid = max(u -> maxid, x);
		int t = (v >> i) & 1; u -> s[t] = new node();
		u = u -> s[t]; p = p ? p -> s[t] : NULL;
	}
	u -> maxid = max(u -> maxid, x);
}
LL query(node *u, int x, int lim) {
	dep(i, 30, 0) {
		int t = (x >> i) & 1;
		if (u -> s[t ^ 1] && u -> s[t ^ 1] -> maxid >= lim) u = u -> s[t ^ 1];
		else u = u -> s[t];
	}
	return (LL)x ^ nw[u -> maxid];
}
LL query(int u, int v, int z) {
	LL res = -INF;
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		res = max(res, query(root[id[u]], z, id[top[u]] - 1));
		u = fa[top[u]];
	}
	if (dep[u] < dep[v]) swap(u, v);
	res = max(res, query(root[id[u]], z, id[v] - 1));
	return res;
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i ++ )
		w[i] = read();
	for (int i = 1, a, b; i < n; i ++ ) {
		a = read(), b = read();
		add(a, b), add(b, a);
	}
	
	dfs1(1, -1, 1), dfs2(1, 1); build();
	for (int i = 1; i <= n; i ++ )
		insert(i);
	
	while (m -- ) {
		int op = read(), x = read(), y, z;
		if (op == 1) {
			z = read();
			printf("%lld\n", query(root[id[x] + sz[x] - 1], z, id[x] - 1));
		}
		else {
			y = read(), z = read();
			printf("%lld\n", query(x, y, z));
		}
	}
	return 0;
}