Untitled

/*
           _                   _         _       __  __  _____ 
     /\   | |            /\   | |       | |     |  \/  |/ ____|
    /  \  | |__   ___   /  \  | |__   __| | ___ | \  / | |     
   / /\ \ | '_ \ / _ \ / /\ \ | '_ \ / _` |/ _ \| |\/| | |     
  / ____ \| |_) | (_) / ____ \| |_) | (_| | (_) | |  | | |____ 
 /_/    \_\_.__/ \___/_/    \_\_.__/ \__,_|\___/|_|  |_|\_____|
*/

// build command:
// g++ -std=gnu++17 -O3 -DDEBUG -g -fsanitize=signed-integer-overflow -fsanitize=bounds-strict -fsanitize=address -fsanitize=integer-divide-by-zero -fsanitize=float-divide-by-zero -fsanitize=pointer-overflow -fsanitize=shift-exponent -fsplit-stack -Wshadow -Wall -fconcepts -Wno-unused-result

// REMEMBER:
// BS, Offline, Persistent SegTree, SQRT, Treap, MaxFlow, FFT, Matrices

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

// DEBUG STUFF
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif


#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.

int getrand(int l,int r) {
	return uniform_int_distribution<int>(l, r)(RNG);
}

const ld eps = 1e-9;
const int mod = 1e9 + 7;
const int oo = 1e9 + 7;
const ll lloo = 1e18 + 7;
const int N = 1e6 + 7;

void solve(int tc) {
	int n,q;
	cin >> n >> q;
	vector<int> a(n+1);
	vector<vector<int>> g(n+1);
	int SQ = sqrt(n)*3;
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	
	for(int i = 0 ; i < n-1 ; i++) {
		int u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	vector<vector<int>> nodes_by_dpth(n+1);
	vector<int> dpth(n+1),par(n+1);
	function<void(int,int)> dfs = [&](int u,int p) {
		nodes_by_dpth[dpth[u]].pb(u);
		for(int v:g[u]) {
			if (v == p) continue;
			par[v] = u;
			a[v] ^= a[u];
			dpth[v] = dpth[u]+1;
			dfs(v,u);
		}
	};
	dfs(1,-1);

	reverse(all(nodes_by_dpth));
	vector<int> SZ(n+1);
	int timer = n;
	vector<vector<int>> G(n+1);
	vector<int> block_dpth;
	int mxsz = 0;
	for(auto nodes:nodes_by_dpth) {
		for(auto u:nodes) {
			SZ[u] = 1;
			for(int v:g[u]) {
				if (v == par[u]) continue;
				SZ[u] += SZ[v];
			}
			
			int sum = 0;
			vector<int> last_nodes;
			vector<int> block_nodes;
			for(int v:g[u]) {
				if (v == par[u]) continue;
				sum += SZ[v];
				last_nodes.pb(v);
				if (sum > SQ) {
					mxsz = max(mxsz,sum);
					int id = ++timer;
					G.pb(last_nodes);
					last_nodes.clear();
					SZ[u] -= sum;
					block_dpth.pb(dpth[u]);
					block_nodes.pb(id);
					sum = 0;
				}
			}
			mxsz = max(mxsz,SZ[u]);
			G[u] = last_nodes;
			for(auto id:block_nodes) G[u].pb(id);
		}
	}
	
	timer++;
	block_dpth.pb(0);
	G.pb({1});
	
	vector<vector<vector<vector<int>>>> cnt(timer-n+1,vector<vector<vector<int>>>(mxsz+1,vector<vector<int>>(20,vector<int>(2))));
	vector<vector<vector<int>>> total(timer-n+1,vector<vector<int>>(20,vector<int>(2)));

	vector<vector<int>> blockg(timer-n+1);

	function<void(int,int)> build_blockg = [&](int u,int id) {
		for(int v:G[u]) {
			if (v > n) {
				blockg[id].pb(v-n-1);
				build_blockg(v,v-n-1);
			}
			else build_blockg(v,id);
		}
	};
	
	build_blockg(timer,timer-n-1);

	function<void(int,int)> build_block = [&](int u,int id) {
		if (u <= n) {
			for(int i = 0 ; i < 20 ; i++) {
				cnt[id][dpth[u]-block_dpth[id]][i][(a[u]>>i)&1]++;
				total[id][i][(a[u]>>i)&1]++;
			}
		}
		for(int v:G[u]) {
			if (v > n) continue;
			build_block(v,id);
		}
	};
	
	for(int id = n+1 ; id <= timer ; id++) {
		build_block(id,id-n-1);
		//dbg(cnt[id-n-1]);
	}
	
	vector<int> xordpth(n+1);
	
	function<void(int,int,int,int)> update_block = [&](int u,int id,int lvl,int x) {
		if (lvl-block_dpth[id] < 0 || lvl-block_dpth[id] > mxsz) return;
		for(int i = 0 ; i < 20 ; i++) {
			if ((x>>i)&1) {
				total[id][i][0] -= cnt[id][lvl-block_dpth[id]][i][0];
				total[id][i][1] -= cnt[id][lvl-block_dpth[id]][i][1];
				swap(cnt[id][lvl-block_dpth[id]][i][0],cnt[id][lvl-block_dpth[id]][i][1]);
				total[id][i][0] += cnt[id][lvl-block_dpth[id]][i][0];
				total[id][i][1] += cnt[id][lvl-block_dpth[id]][i][1];
			}
		}
	};
	
	function<ll(int,int)> query_block = [&](int id,int x) {
		ll ret = 0;
		for(int i = 0 ; i < 20 ; i++) {
			ret += (1<<i)*(total[id][i][1^((x>>i)&1)]);
		}
		for(int v:blockg[id]) ret += query_block(v,x);
		dbg(id,ret);
		return ret;
	};
	
	function<ll(int,int)> query = [&](int u,int x) {
		ll ret = a[u]^xordpth[dpth[u]]^x;
		
		for(int v:G[u]) {
			if (v > n) {
				ret += query_block(v-n-1,x);
			}
			else ret += query(v,x);
		}
		dbg(u,G[u]);
		return ret;
	};
	
	for(int i = 0 ; i < q ; i++) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int l,r,x;
			cin >> l >> r >> x;
			xordpth[l] ^= x;
			for(int id = n+1 ; id <= timer ; id++) {
				update_block(id,id-n-1,l,x);
			}
		} else if (ty == 2) {
			int u;
			cin >> u;
			int x = 0;
			if (par[u] > 0) {
				x = a[par[u]]^xordpth[dpth[par[u]]];
			}
			cout << query(u,x) << '\n';
		}
	}
	
}

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	// freopen("in","r",stdin);
	// freopen("out","w",stdout);
	int T = 1;
	cin >> T;
	for(int i = 0 ; i < T ; i++) solve(i+1);
	return 0;
}