#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using i64 = long long;
using f64 = long double;
using ui64 = unsigned long long;
using pII = pair<int,int>;
using pLL = pair<i64,i64>;
mt19937 rng32(time(0));
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
int t,n,q,a[100009],b[100009],bb[100009][10],seg[500009][10],lazy[500009][10];
int ci,cp,sz[100009],head[100009],par[100009],pos[100009],rL[500009],rR[500009];
vector<int> adj[100009];
void buildrange(int node,int l,int r)
{
if(l==r) rL[node]=l,rR[node]=r;
else
{
buildrange(2*node,l,(l+r)/2);
buildrange(2*node+1,(l+r)/2+1,r);
rL[node]=rL[2*node];rR[node]=rR[2*node+1];
}
}
void build(int node,int l,int r,int8_t _b)
{
lazy[node][_b]=0;
if(l==r) seg[node][_b]=bb[l][_b];
else
{
build(2*node,l,(l+r)/2,_b);
build(2*node+1,(l+r)/2+1,r,_b);
seg[node][_b]=seg[2*node][_b]+seg[2*node+1][_b];
}
}
void down(int node,int8_t _b)
{
if(lazy[node][_b]&1)
{
seg[2*node][_b]=rR[2*node]-rL[2*node]+1-seg[2*node][_b];
seg[2*node+1][_b]=rR[2*node+1]-rL[2*node+1]+1-seg[2*node+1][_b];
}
lazy[2*node][_b]^=lazy[node][_b];
lazy[2*node+1][_b]^=lazy[node][_b];
lazy[node][_b]=0;
}
void update(int node,int tl,int tr,int l,int r,bool v,int8_t _b)
{
if(tr<l or r<tl) return;
if(l<=tl and tr<=r)
{
if(v&1) seg[node][_b]=rR[node]-rL[node]+1-seg[node][_b];
lazy[node][_b]^=v;
return;
}
down(node,_b);
update(2*node,tl,(tl+tr)/2,l,r,v,_b);
update(2*node+1,(tl+tr)/2+1,tr,l,r,v,_b);
seg[node][_b]=seg[2*node][_b]+seg[2*node+1][_b];
}
void real_update(int l,int r,int v){
for(short i=0;i<10;++i) update(1,1,n,l,r,(v>>i)&1,i);
}
int sum(int node,int tl,int tr,int l,int r,int8_t _b)
{
if(tr<l or r<tl) return 0;
if(l<=tl and tr<=r) return seg[node][_b];
down(node,_b);
return sum(2*node,tl,(tl+tr)/2,l,r,_b)+sum(2*node+1,(tl+tr)/2+1,tr,l,r,_b);
}
int real_sum(int l,int r){
int s=0;
for(short i=0;i<10;++i) s+=(1<<i)*sum(1,1,n,l,r,i);
return s;
}
void DFS(int u,int pu)
{
par[u]=pu; sz[u]=1;
for(int v:adj[u])
{
if(v!=pu)
{
DFS(v,u);
sz[u]+=sz[v];
}
}
}
void HLD(int u,int pu)
{
b[ci]=u;pos[u]=ci;++ci;
head[u]=b[cp];
int mx=-1;
for(int v:adj[u])
if(v!=pu and sz[v]>sz[mx]) mx=v;
if(mx<0) {cp=ci;return;}
HLD(mx,u);
for(int v:adj[u])
if(v!=mx and v!=pu) HLD(v,u);
}
int LCA(int u,int v)
{
while(head[u]!=head[v])
{
if(sz[head[u]]<sz[head[v]]) u=par[head[u]];
else v=par[head[v]];
}
return sz[u]>sz[v]?u:v;
}
void even_real_update(int u,int v,int val)
{
int L=LCA(u,v);
while(head[u]!=head[L])
{
real_update(pos[head[u]],pos[u],val);
u=par[head[u]];
}
while(head[v]!=head[L])
{
real_update(pos[head[v]],pos[v],val);
v=par[head[v]];
}
if(sz[u]>sz[v]) real_update(pos[u],pos[v],val);
else real_update(pos[v],pos[u],val);
}
int even_real_sum(int u,int v)
{
int L=LCA(u,v),res=0;
while(head[u]!=head[L])
{
res+=real_sum(pos[head[u]],pos[u]);
u=par[head[u]];
}
while(head[v]!=head[L])
{
res+=real_sum(pos[head[v]],pos[v]);
v=par[head[v]];
}
if(sz[u]>sz[v]) res+=real_sum(pos[u],pos[v]);
else res+=real_sum(pos[v],pos[u]);
return res;
}
void azarathmetrionzithos()
{
cin>>n; ci=cp=1;
for(int i=1;i<=n;++i)
{
cin>>a[i];
adj[i].clear();
adj[i].shrink_to_fit();
}
for(int u,v,i=1;i<n;++i)
{
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
adj[1].push_back(0);
DFS(1,0); sz[0]=1+sz[1];
HLD(1,0); buildrange(1,1,n);
for(int i=1;i<=n;++i)
for(int8_t j=0;j<10;++j) bb[i][j]=(a[b[i]]>>j)&1;
for(int8_t i=0;i<10;++i) build(1,1,n,i);
cin>>q;
for(int cmd,u,v,p;q>0;--q)
{
cin>>cmd;
if(cmd==1)
{
cin>>u>>v>>p;
even_real_update(u,v,p);
}
else
{
cin>>u>>v;
cout<<even_real_sum(u,v)<<'\n';
}
}
exit(0);
}
signed main()
{
if(fopen("XORTREE.INP","r"))
{
freopen("XORTREE.INP","r",stdin);
freopen("XORTREE.OUT","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--) azarathmetrionzithos();
}
/*
........................
..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::..
..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+.
..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:.
..:-+*%@@@@@@@%%%##########################################%@@@@+:.
..:=+%@@@@@@%%#####################################################@@@@+..
....-+%@@@@@@%#############################################################@@@@=..
..=#@@@@@%%###################################################################%@@@%-.
.:+#%@@@@%%#########################################################################%@@@#:.
.:=*%@@@%%###############################################################################%@@@@-.
..-*%@@@%%#####################################################################################%@@@=.
..+@@@@###########################################################################################%@@@*..
.*@@@#*##############################################################################################@@@%.
.+@@@#**################################################################################################@@@%:.
.-%@@#**####%##############################################################################################%@@%:.
.+@@#***###%%################################################################################################%@@@-.
:#@%****###%%*#################################################################################################%@@@-.
-@@%****###@%*###################################################################################################%@@@-.
-@@#***###%@#*#####################################################################################################%@@@=.
-@@#***###@@#*#######################################################################################################@@@%-.
:@@#***###@%**#########################################################################################################@@@+.
:%@#***##%@%**##########################################################################################################%@@@.
.#@%***##%@%**############################################################################################################%@@*.
.+@%***##@@#**##############################################################################################@@##############@@@:.
:@@***##@@#**###############################################################################################@@@%############%@@#.
.%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=.
.*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%.
-@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=.
.#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%.
=@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=.
.@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%.
.#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@-
..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#.
.-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:.
...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*.
..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@.
.#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+.
:#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%.
.+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-.
.+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#.
.:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:.
.....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*.
.=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@.
.%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=.
.+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%.
.@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=.
.+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%.
:@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+.
.*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:.
:@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#.
.*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*.
.=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=.
-@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=.
.+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=.
.-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+.
..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#.
...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-.
.-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*..
-@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=.
.:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+.
.+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:.
.:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+.
.+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+.
.#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=.
.-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-.
..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:.
.=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=..
.=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-.
.=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+..
.-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:.
..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+..
.:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:.
..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-.
.:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=..
.-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=..
...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-..
...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:..
..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=..
..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:..
..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-.
..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-..
.....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:...
..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:..
...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:..
...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:..
...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:..
.*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:..
.@@%****##########@#====%%###@##@%%%@@@%-:....
-@@#****##########@#===+@#***@%=@%###@@%.
=@@*****##########%@===#@#***%@=%@###%@@-
.*@@*****###########@*==*%%%%%@@+@%###%@@+.
.@@%****############%@+=====++==%@#####@@%.
=@@#****#############@@========#@######@@@.
.*@@*****############@@%@+=====*@#######@@@=.
.%@@*****###########%@##@@#===#@########%@@*.
-@@%****###########%@%##@%%%*#@##########@@%.
=@@#****###########@%###@##%@@###########@@@-.
+@@*****##########@@###%@##%@@###########@@@+.
.%@@****##########@@####@%##%@@###########%@@%.
-@@%****#########@@#####@###%@@############@@@:
=@@#****########%@#####%@####@@############@@@=.
#@@*****#######%@######@%####@@############%@@#.
.%@@****#######%@######%@#####@@############%@@%.
-@@%****######%@#######%@#####@@%############@@@-.
=@@#****#####%@########@%#####@@%############@@@+.
+@@#****####%@########%@######@@%############%@@#.
.%@@****####%@#########@@######@@%############%@@@:
:@@%****###%@##########@%######@@%#############@@@=.
=@@%****##%%##########%@#######@@%#############@@@*.
#@@#****#%%###########@@#######@@@#############%@@%.
.%@@*****%############%@%#######@@@#############%@@@:
-@@@****##############@@########%@@##############@@@+.
-@@%****##############@%########%@@##############@@@#.
.*@@#****#############@@#########%@@##############%@@@:
.%@@*****#############@%#########%@@##############%@@@-.
:@@@*****############%@##########%@@###############@@@*.
-@@%*****############@%##########%@@###############@@@%.
#@@#****############%@############@@###############%@@@:
.%@@#****############@%############@@%###############@@@=.
:@@@*****###########%@#############@@%###############@@@*.
-@@%*****###########@%#############@@%###############@@@%.
=@@%*****##########%@##############@@%###############%@@@:
.#@@#*****##########@%##############@@%################@@@+.
:@@@*****###########@###############@@%################@@@#.
*/