#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct IO{
	static const int S=1<<21;
	char buf[S],*p1,*p2;int st[105],Top;
	~IO(){clear();}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
	inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
	IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n');return *this;}
	template<typename T> IO&operator >> (T&x){
		x=0;bool f=0;char ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
		while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
		f?x=-x:0;return *this;
	}
	IO&operator << (const char c){pc(c);return *this;}
	template<typename T> IO&operator << (T x){
		if(x<0) pc('-'),x=-x;
		do{st[++st[0]]=x%10,x/=10;}while(x);
		while(st[0]) pc('0'+st[st[0]--]);return *this;
	}
}fin,fout;
const int N=2e5+5,E=N<<1,MK=10;
const LL inf=1ll<<60;
int T,n,q;LL a[N],asonMK[N];
int son[E],nxt[E],lnk[N],tot;
void add_e(int x,int y){
    son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot;
}
#define v son[j]
int sonL[MK+1][N],sonR[MK+1][N],bfs_idx[N];
int Q[N];bool vis[N];
void bfs(int x){
	int hed=0,til=0;
	Q[til=1]=1;vis[1]=1;
	while(hed<til){
		int x=Q[++hed];
		bfs_idx[hed]=x;
		for(int i=0;i<=MK;i++) sonL[i][x]=1<<30,sonR[i][x]=0;
		for(int j=lnk[x];j;j=nxt[j]) if(!vis[v]){
			vis[v]=1;Q[++til]=v;
		}
	}
}
int In[N],Ou[N],idx,fa[MK+1][N],dfs_idx[N];
void dfs(int x){
    In[x]=++idx;
    dfs_idx[idx]=x;
	sonL[0][x]=sonR[0][x]=idx;
	asonMK[x]=-inf;
	for(int i=2;i<=MK;i++) fa[i][x]=fa[1][fa[i-1][x]];
	if(fa[MK][x]) asonMK[fa[MK][x]]=max(asonMK[fa[MK][x]],a[x]);
    for(int j=lnk[x];j;j=nxt[j]) 
        if(v!=fa[1][x]){
            fa[1][v]=x;dfs(v);
			for(int i=1;i<=MK;i++){
				sonL[i][x]=min(sonL[i][x],sonL[i-1][v]);
				sonR[i][x]=max(sonR[i][x],sonR[i-1][v]);
			}
        }
    Ou[x]=idx;
}
#undef v
struct Node{LL mx,tag;};
struct SegTree{
	Node T[N<<2];
	void pushd(int k){
		if(T[k].tag){
			T[k<<1].tag+=T[k].tag;
			T[k<<1|1].tag+=T[k].tag;
			T[k<<1].mx+=T[k].tag;
			T[k<<1|1].mx+=T[k].tag;
			T[k].tag=0;
		}
	}
	void pushu(int k){
		T[k].mx=max(T[k<<1].mx,T[k<<1|1].mx);
	}
	void build(int k,int l,int r,bool isA){
		T[k].tag=0;
		if(l==r){
			if(isA) T[k].mx=a[bfs_idx[l]];
			else T[k].mx=asonMK[dfs_idx[l]];
			return;
		}
		int mid=l+r>>1;
		build(k<<1,l,mid,isA),build(k<<1|1,mid+1,r,isA);
		pushu(k);
	}
	void modify(int k,int l,int r,int x,LL v){
		if(l==r){T[k].mx=v+T[k].tag;return;} 
		int mid=l+r>>1;pushd(k);
		(x<=mid)?modify(k<<1,l,mid,x,v):modify(k<<1|1,mid+1,r,x,v);
		pushu(k);
	}
	void modify(int k,int l,int r,int tl,int tr,LL v){
		if(l>tr||r<tl) return;if(l>=tl&&r<=tr){T[k].mx+=v,T[k].tag+=v;return;}
		int mid=l+r>>1;pushd(k);
		modify(k<<1,l,mid,tl,tr,v),modify(k<<1|1,mid+1,r,tl,tr,v);
		pushu(k);
	}
	LL query(int k,int l,int r,int x){
		if(l==r) return T[k].tag;pushd(k);int mid=l+r>>1;
		return (x<=mid)?query(k<<1,l,mid,x):query(k<<1|1,mid+1,r,x);
	}
	LL query(int k,int l,int r,int tl,int tr){
		if(l>tr||r<tl) return -inf;if(l>=tl&&r<=tr) return T[k].mx;
		pushd(k);int mid=l+r>>1;
		return max(query(k<<1,l,mid,tl,tr),query(k<<1|1,mid+1,r,tl,tr));
	}
}A,B;
LL UpdDisk(int tl,int tr,LL v){
	if(tl>tr) return -inf;
	A.modify(1,1,n,tl,tr,v);
	int faMK=fa[MK][bfs_idx[tl]];
	if(faMK) B.modify(1,1,n,In[faMK],A.query(1,1,n,sonL[MK][faMK],sonR[MK][faMK]));
	return A.query(1,1,n,tl,tr)+(faMK?B.query(1,1,n,In[faMK]):0);
}
LL QryDisk(int x,int k,LL v,int nl,int nr){
	LL ret=-inf;
	int l=sonL[k][x],r=sonR[k][x];
	if(l>nr||r<nl) ret=max(ret,UpdDisk(l,r,v));
	else ret=max(ret,max(UpdDisk(l,nl-1,v),UpdDisk(nr+1,r,v)));
	if(k>1) ret=max(ret,QryDisk(fa[1][x],k-1,v,sonL[k-2][x],sonR[k-2][x]));
	else if(k) ret=max(ret,QryDisk(fa[1][x],k-1,v,0,0));
	return ret; 
}
LL QryMDisk(int x,int k,LL v){
	LL ret=-inf;if(k<0) return ret;
	int l=sonL[k][x],r=sonR[k][x];
	ret=max(ret,UpdDisk(l,r,v));
	if(!fa[1][x]){
		for(int i=k-1;~i;i--){
			l=sonL[i][x],r=sonR[i][x];
			ret=max(ret,UpdDisk(l,r,v));
		}
	}else if(k){
		l=sonL[k-1][x],r=sonR[k-1][x];
		ret=max(ret,max(UpdDisk(l,r,v),QryMDisk(fa[1][x],k-1,v)));
	}
	return ret;
}
LL QrySub(int x,LL v){
	LL ret=-inf;
	for(int i=0;i<=MK;i++) ret=max(ret,UpdDisk(sonL[i][x],sonR[i][x],v));
	B.modify(1,1,n,In[x],Ou[x],v);
	ret=max(ret,B.query(1,1,n,In[x],Ou[x]));
	return ret;
}
void clear(){
	tot=idx=0;
	for(int i=1;i<=n;i++) lnk[i]=vis[i]=0;
}
int main(){
	fin>>T;
	while(T--){
		clear();
		fin>>n>>q;
		if(n>10000) break;
		for(int i=1;i<=n;i++) fin>>a[i];
		for(int i=1;i<n;i++){
			int x,y;fin>>x>>y;
			add_e(x,y),add_e(y,x);
		}
		bfs(1);dfs(1);
		A.build(1,1,n,1);
		B.build(1,1,n,0);
		while(q--){
			int op,x,k;LL v,ans;
			fin>>op;
			switch(op){
				case 1:{
					fin>>x>>k>>v;
					ans=QryDisk(x,k,v,0,0);
					break;
				}
				case 2:{
					fin>>x>>k>>v;
					ans=QryMDisk(x,k,v);
					break;
				}
				case 3:{
					fin>>x>>v;
					ans=QrySub(x,v);
					break;
				}
			}
			if(ans==-inf) fout<<'G'<<'G'<<'\n';
			else fout<<ans<<'\n';
		}
	}
	return 0;
}