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

using ll=int64_t;
//#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	#ifdef int
	scanf("%" SCNd64,&i);
	#else
	scanf("%d",&i);
	#endif
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	#ifdef int
	printf("%" PRId64,x);
	#else
	printf("%d",x);
	#endif
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

#ifdef int
const int inf=LLONG_MAX/3;
#else
const int inf=INT_MAX/2-100;
#endif

enum ClusterType{
	NONE,
	BASE,
	RAKE,
	COMPRESS,
	HARDRAKE
};
template<class ClusterInfoUtil>
struct TopTree{
	using Info=typename ClusterInfoUtil::Info;
	struct Cluster{
		TopTree* belongingTree;
		ClusterType type;
		Cluster *l,*r,*m,*p,*link;
		Info info,tmpInfo;
		int a,b;
		Cluster(TopTree* tree){
			belongingTree=tree;
			Clear();
		}
		void Clear(){
			type=NONE;
			l=nullptr;
			r=nullptr;
			m=nullptr;
			p=nullptr;
			link=nullptr;
			info=Info();
			tmpInfo=Info();
			a=-1;
			b=-1;
		}
		void UpdateHandles(){
			cerr<<a<<" "<<b<<endl;
			if(type==BASE){
				belongingTree->handles[a]=this;
				belongingTree->handles[b]=this;
			}else if(type==COMPRESS){
				belongingTree->handles[l->a]=this;
				belongingTree->handles[l->b]=this;
				belongingTree->handles[r->a]=this;
				belongingTree->handles[r->b]=this;
			}
		}
		void Update(){
			if(type==COMPRESS){
				REACH;
				if(m){
					cerr<<m<<endl;
					REACH;
					cerr<<m->a<<endl;
					REACH;
					tmpInfo=Info();
					REACH;
					cerr<<l<<endl;
					tmpInfo.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
					REACH;
				}
				REACH;
				a=l->a;
				b=r->b;
				assert(l->b==r->a);
				REACH;
				UpdateHandles();
				REACH;
				info=Info();
				info.Join(a,b,l->a,l->b,m?tmpInfo:l->info,r->a,r->b,r->info,COMPRESS);
			}else if(type==RAKE){
				a=r->a;
				b=r->b;
				info=Info();
				info.Join(a,b,l->a,l->b,l->info,r->a,r->b,r->info,RAKE);
			}else if(type==HARDRAKE){
				int la=l->a,lb=l->b;
				int ra=r->a,rb=r->b;
				if(la==ra||la==rb)swap(la,lb);
				if(lb==ra)swap(ra,rb);
				a=ra;
				b=rb;
				info=Info();
				info.Join(a,b,la,lb,l->info,ra,rb,r->info,RAKE);
			}
		}
		void Reverse(){
			swap(a,b);
		}
		void Normalize(){
			if(type==BASE){
				assert(!l);
				assert(!r);
			}else{
				assert(l);
				assert(r);
				if(type==COMPRESS){
					REACH;
					bool updMid=false;
					if(r->a==a||r->b==a){
						swap(l,r);
						updMid=true;
					}
					if(l->a!=a)l->Reverse();
					if(r->b!=b)r->Reverse();
					if(m&&updMid){
						tmpInfo=Info();
						tmpInfo.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
					}
					info.Split(a,b,l->a,l->b,m?tmpInfo:l->info,r->a,r->b,r->info,COMPRESS);
					if(m)tmpInfo.Split(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
				}else if(type==RAKE){
					REACH;
					assert(!m);
					info.Split(a,b,l->a,l->b,l->info,r->a,r->b,r->info,RAKE);
				}else if(type==HARDRAKE){
					REACH;
					assert(!m);
					int la=l->a,lb=l->b;
					int ra=r->a,rb=r->b;
					if(la==ra||la==rb)swap(la,lb);
					if(lb==ra)swap(ra,rb);
					info.Split(a,b,la,lb,l->info,ra,rb,r->info,RAKE);
				}
			}
		}
		int Pos(){
			Cluster *x=p?p:link;
			if(!x)return 0;
			else if(x->l==this)return -1;
			else if(x->r==this)return 1;
			else if(x->m==this)return -2;
			assert(false);
		}
		void Rotate(){
			//CheckNormalized();
			Cluster *q=p,*c;
			if(Pos()==1){
				c=l;
				l=q;
				q->r=c; 
			}else{
				c=r;
				r=q;
				q->l=c;
			}
			REACH;
			if(c){
				if(c->p)c->p=q;
				if(c->link)c->link=q;
			}
			REACH;
			int w=p->Pos();
			link=p->link;
			p=p->p;
			REACH;
			q->link=nullptr;
			q->p=this;
			REACH;
			Cluster *x=p?p:link;
			if(x){
				if(w==1)x->r=this;
				else if(w==-1)x->l=this;
				else if(w==-2)x->m=this;
			}
			REACH;
			q->Update();
			REACH;
		}
		void CheckNormalized(){
			if(type==BASE){
				assert(!l);
				assert(!r);
			}else{
				assert(l);
				assert(r);
				if(type==COMPRESS){
					assert(a==l->a);
					assert(l->b==r->a);
					assert(r->b==b);
					if(m)assert(l->b==m->b);
				}else if(type==RAKE){
					assert(!m);
					assert(a==r->a);
					assert(b==r->b);
					assert(l->b==r->b);
				}else if(type==HARDRAKE){
					assert(!m);
					int la=l->a,lb=l->b;
					int ra=r->a,rb=r->b;
					if(la==ra||la==rb)swap(la,lb);
					if(lb==ra)swap(ra,rb);
					assert(a==ra);
					assert(b==rb);
					assert(lb==rb);
				}
			}
		}
		void Splay(Cluster* guard){
			assert(type!=BASE);
			REACH;
			while(p&&p!=guard){
				Cluster *q=p->p;
				REACH;
				if(q&&q!=guard){
					REACH;
					if(Pos()==p->Pos()){
						REACH;
						p->Rotate();
					}else{
						REACH;
						Rotate();
					}
					REACH;
					Rotate();
					REACH;
				}else{
					REACH;
					Rotate();
				}
			}
			REACH;
			Update();
		}
		void Destroy(){
			ClusterInfoUtil::Destroy(a,b,info);
		}
	};
	vector<Cluster*> handles;
	vector<Cluster> clusterBuf;
	vector<Cluster*> ptrBuf;
	vi deg;
	vector<Cluster*> hardRakeClusters,needUpdateClusters;
	TopTree(){}
	TopTree(int n){
		Init(n);
	}
	int vertNum,edgeNum;
	void Init(int n){
		int s=n*2+10;
		clusterBuf=vector<Cluster>(s,Cluster(this));
		REP(i,s)ptrBuf.PB(clusterBuf.data()+i);
		deg=vi(n,0);
		handles=vector<Cluster*>(n,nullptr);
		vertNum=n;
		edgeNum=0;
	}
	Cluster* GetNew(){
		Cluster *res=ptrBuf.back();
		ptrBuf.pop_back();
		res->Clear();
		return res;
	}
	void Recycle(Cluster* ptr){
		ptrBuf.PB(ptr);
	}
	void ClearHardRakeClusters(){
		while(!hardRakeClusters.empty()){
			Cluster* x=hardRakeClusters.back();
			hardRakeClusters.pop_back();
			x->Normalize();
			Recycle(x);
		}
		while(!needUpdateClusters.empty()){
			Cluster* x=needUpdateClusters.back();
			needUpdateClusters.pop_back();
			x->Update();
		}
	}
	void Rectify(Cluster* x,Cluster* guard){
		Cluster* p=x->p?x->p:x->link;
		if(p!=nullptr){
			cerr<<x->p<<endl;
			REACH;
			Rectify(p,guard);
			if(p==guard&&p->r==x){
				REACH;
				p->Reverse();
				p->Normalize();
				REACH;
			}
		}
		REACH;
		x->Normalize();
		REACH;
	}
	Cluster* CreateCompressCluster(Cluster*l,Cluster*r,Cluster*m){
		assert(l&&r);
		auto p=GetNew();
		p->type=COMPRESS;
		p->l=l;
		l->p=p;
		l->link=nullptr;
		p->r=r;
		r->p=p;
		r->link=nullptr;
		p->m=m;
		if(m){
			m->p=nullptr;
			m->link=p;
		}
		p->Update();
		return p;
	}
	Cluster* CreateRakeCluster(Cluster*l,Cluster*r){
		if(!l)return r;
		if(!r)return l;
		auto p=GetNew();
		p->type=RAKE;
		p->l=l;
		if(l->type==RAKE){
			l->p=p;
			l->link=nullptr;
		}else{
			l->p=nullptr;
			l->link=p;
		}
		p->r=r;
		if(r->type==RAKE){
			r->p=p;
			r->link=nullptr;
		}else{
			r->p=nullptr;
			r->link=p;
		}
		p->Update();
		return p;
	}
	Cluster* CreateHardRakeCluster(Cluster*l,Cluster*r){
		if(!l)return r;
		auto p=GetNew();
		hardRakeClusters.PB(p);
		p->type=HARDRAKE;
		p->l=l;
		p->r=r;
		p->Update();
		return p;
	}
	void SoftExpose(int v,Cluster* guard){
		assert(deg[v]);
		if(handles[v]==guard)return;
		cerr<<v<<endl;
		Rectify(handles[v],guard);
		REACH;
		Cluster *x=handles[v],*tmp=x;
		if(x->type==COMPRESS)x->Splay(guard);
		REACH;
		while(x->link){
			Cluster* p=x->link;
			if(p->type==RAKE){
				p->Splay(nullptr);
				if(x->link!=p)
					x->link->Splay(p);
				x=p;
				assert(x->link);
			}
			x=x->link;
			x->Splay(guard);
		}
		REACH;
		x=tmp;
		while(x->link){
			Cluster* m=nullptr;
			Cluster* y=x->link;
			cerr<<y<<" "<<guard<<endl;
			if(y->type==RAKE){
				Cluster*p=x->link;
				if(x->Pos()<0){
					m=p->r;
				}else{
					m=p->l;
				}
				y=p->link;
				if(p->p){
					Cluster*q=p->p;
					if(p->Pos()<0){
						m=CreateRakeCluster(m,q->r);
					}else{
						m=CreateRakeCluster(m,q->l);
					}
					y=q->link;
					Recycle(q);
				}
				Recycle(p);
			}
			REACH;
			m=CreateRakeCluster(m,y->l);
			y->l->UpdateHandles();
			y->l=x;
			x->p=y;
			x->link=nullptr;
			y->m=m;
			assert(m);
			m->p=nullptr;
			m->link=y;
			y->Update();
			x=y;
		}
		cerr<<x<<endl;
		REACH;
		cerr<<tmp<<endl;
		cerr<<tmp->type<<" "<<tmp->a<<" "<<tmp->b<<endl;
		if(tmp->type==BASE)tmp=tmp->p;
		if(tmp){
			assert(tmp->type==COMPRESS);
			tmp->Splay(guard);
		}
		REACH;
		if(guard)guard->Update();
		REACH;
	}
	bool SoftExpose(int a,int b){
		assert(deg[a]<=deg[b]);
		if(deg[b]==0){
			return false;
		}else if(deg[a]==0){
			SoftExpose(b,nullptr);
			if(handles[b]->a==b){
				handles[b]->Reverse();
				handles[b]->Normalize();
			}
			handles[b]->CheckNormalized();
			return false;
		}else if(deg[b]==1){
			REACH;
			SoftExpose(b,nullptr);
			if(handles[b]->a==b){
				handles[b]->Reverse();
				handles[b]->Normalize();
			}
			handles[b]->CheckNormalized();
			REACH;
			SoftExpose(a,nullptr);
			if(handles[a]==handles[b]){
				cerr<<a<<" "<<b<<endl;
				cerr<<handles[a]->a<<" "<<handles[a]->b<<endl;
				assert(handles[a]->a==a);
				assert(handles[a]->b==b);
				handles[a]->CheckNormalized();
				return true;
			}else{
				if(handles[a]->a==a){
					handles[a]->Reverse();
					handles[a]->Normalize();
				}
				handles[a]->CheckNormalized();
				handles[b]->CheckNormalized();
				return false;
			}
		}else{
			cerr<<a<<" "<<b<<endl;
			cerr<<handles[a]<<" "<<handles[b]<<endl;
			cerr<<handles[b]->a<<" "<<handles[b]->b<<endl;
			SoftExpose(b,nullptr);
			assert(handles[b]->a!=b&&handles[b]->b!=b);
			handles[b]->CheckNormalized();
			cerr<<handles[b]->a<<" "<<handles[b]->b<<endl;
			cerr<<handles[a]<<" "<<handles[b]<<endl;
			SoftExpose(a,handles[b]);
			cerr<<handles[a]<<" "<<handles[b]<<endl;
			if(handles[a]==handles[b]){
				if(handles[a]->b==a){
					handles[a]->Reverse();
					handles[a]->Normalize();
				}
				cerr<<handles[a]->a<<" "<<handles[a]->b<<endl;
				assert(handles[a]->a==a);
				handles[a]->CheckNormalized();
				return true;
			}else if(handles[a]==handles[b]->l){
				handles[b]->CheckNormalized();
				handles[a]->CheckNormalized();
				assert(handles[a]->b==b);
				return true;
			}else{
				if(handles[a]->a==a){
					handles[a]->Reverse();
					handles[a]->Normalize();
				}
				handles[a]->CheckNormalized();
				handles[b]->CheckNormalized();
				return false;
			}
		}
	}
	void SoftExpose(int v){
		SoftExpose(v,nullptr);
		if(handles[v]->a==v){
			handles[v]->Reverse(); 
			handles[v]->Normalize();
		}
		handles[v]->CheckNormalized();
	}
	Cluster* HardExpose(int a,int b){
		assert(deg[a]<=deg[b]);
		if(deg[b]==1){
			assert(handles[a]==handles[b]);
			assert(handles[a]->a==a);
			assert(handles[a]->b==b);
			return handles[a];
		}else if(deg[a]==1){
			assert(handles[a]==handles[b]);
			handles[b]->CheckNormalized();
			needUpdateClusters.PB(handles[b]);
			auto x=handles[b]->l;
			assert(x->a==a&&x->b==b);
			x=CreateHardRakeCluster(handles[b]->m,x);
			x=CreateHardRakeCluster(handles[b]->r,x);
			return x;
		}else{
			handles[a]->CheckNormalized();
			handles[b]->CheckNormalized();
			needUpdateClusters.PB(handles[b]);
			needUpdateClusters.PB(handles[a]);
			auto x=handles[a]->r;
			assert(x->a==a&&x->b==b);
			x=CreateHardRakeCluster(handles[a]->l,x);
			x=CreateHardRakeCluster(handles[a]->m,x);
			x=CreateHardRakeCluster(handles[b]->m,x);
			x=CreateHardRakeCluster(handles[b]->r,x);
			return x;
		}
	}
	Cluster* HardExpose(int v){
		return HardExpose(handles[v]->a,v);
	}
	Cluster* ExposePath(int a,int b){
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		bool connected=SoftExpose(a,b);
		if(!connected)return nullptr;
		return HardExpose(a,b);
	}
	Info* Expose(int a,int b){
		Cluster*x=ExposePath(a,b);
		if(x)return &(x->info);
		else return nullptr;
	}
	Cluster* ExposeVertex(int v){
		ClearHardRakeClusters();
		SoftExpose(v);
		if(deg[v]==0)return nullptr;
		return HardExpose(v);
	}
	pair<Info*,int> Expose(int v){
		Cluster*x=ExposeVertex(v);
		if(x)return MP(&(x->info),x->a);
		else return MP(nullptr,-1);
	}
	bool Connected(int a,int b){
		cerr<<"connected "<<a<<" "<<b<<endl;
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		return SoftExpose(a,b);
	}
	template <class... Args>
	bool Link(int a,int b,Args... args){
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		cerr<<"link "<<a<<" "<<b<<endl;
		bool connected=SoftExpose(a,b);
		REACH;
		if(connected)return false;
		Cluster* u=handles[a],*v=handles[b];
		Cluster* x=GetNew();
		x->type=BASE;
		x->a=a;
		x->b=b;
		x->info.Create(a,b,args...);
		x->UpdateHandles();
		Cluster* y=nullptr;
		if(deg[a]==0){
			y=x;
		}else if(deg[a]==1){
			assert(u->b==a);
			y=CreateCompressCluster(u,x,nullptr);
		}else{
			u->CheckNormalized();
			assert(u->l->b==a);
			u->r->Reverse();
			u->r->UpdateHandles();
			y=CreateCompressCluster(u->l,x,CreateRakeCluster(u->r,u->m));
			Recycle(u);
		}
		REACH;
		if(deg[b]==0){
			//do nothing
		}else if(deg[b]==1){
			assert(v->b==b);
			v->Reverse();
			v->Normalize();
			CreateCompressCluster(y,v,nullptr);
		}else{
			v->CheckNormalized();
			assert(v->r->a==b);
			v->l->UpdateHandles();
			CreateCompressCluster(y,v->r,CreateRakeCluster(v->m,v->l));
			Recycle(v);
		}
		deg[a]++;
		deg[b]++;
		edgeNum++;
		return true;
	}
	pair<Cluster*,Cluster*> SplitMiddleChild(Cluster*x){
		if(x->type!=RAKE)return MP(x,nullptr);
		while(x->type==RAKE)x=x->l;
		assert(!x->p);
		assert(x->link);
		x->link->Splay(nullptr);
		Cluster* tmp=x->link;
		pair<Cluster*,Cluster*>  res=MP(tmp->l,tmp->r);
		Recycle(tmp);
		return res;
	}
	bool Cut(int a,int b){
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		cerr<<"cut "<<a<<" "<<b<<endl;
		bool connected=SoftExpose(a,b);
		if(!connected)return false;
		Cluster *u=handles[a],*v=handles[b];
		if(deg[b]==1){
			if(u->type!=BASE)return false;
			u->Destroy();
			Recycle(u);
			handles[a]=nullptr;
			handles[b]=nullptr;
		}else if(deg[a]==1){
			if(v->l->type!=BASE)return false;
			if(deg[b]==2){
				v->r->p=nullptr;
				v->r->UpdateHandles();
			}else{
				pair<Cluster*,Cluster*> z=SplitMiddleChild(v->m);
				CreateCompressCluster(z.first,v->r,z.second);
			}
			v->l->Destroy();
			Recycle(v->l);
			Recycle(v);
			handles[a]=nullptr;
		}else{
			assert(v->l==u);
			if(u->r->type!=BASE)return false;
			if(deg[a]==2){
				u->l->p=nullptr;
				u->l->UpdateHandles();
			}else{
				pair<Cluster*,Cluster*> z=SplitMiddleChild(u->m);
				z.first->Reverse();
				CreateCompressCluster(u->l,z.first,z.second);
			}
			if(deg[b]==2){
				v->r->p=nullptr;
				v->r->UpdateHandles();
			}else{
				pair<Cluster*,Cluster*> z=SplitMiddleChild(v->m);
				CreateCompressCluster(z.first,v->r,z.second);
			}
			u->r->Destroy();
			Recycle(u->r);
			Recycle(u);
			Recycle(v);
		}
		deg[a]--;
		deg[b]--;
		edgeNum--;
		return true;
	}
	int NumofVertices(){
		return vertNum;
	}
	int NumofEdges(){
		return edgeNum;
	}
	void Show(){
		cerr<<"Top Tree Structure"<<endl;
		REP(i,vertNum){
			if(handles[i])
				cerr<<i<<" "<<handles[i]<<" "<<handles[i]->a<<" "<<handles[i]->b<<" "<<handles[i]->l<<" "<<handles[i]->r<<endl;
			else
				cerr<<i<<" isolated"<<endl;
		}
	}
};

struct InfoBase{
	private:
	int vert[2];
	public:
	InfoBase(){
		ONE(vert);
	}
	inline int idx(int v){
		if(vert[0]==v)return 0;
		if(vert[1]==v)return 1;
		if(vert[0]==-1){
			vert[0]=v;
			return 0;
		}
		if(vert[1]==-1){
			vert[1]=v;
			return 1;
		}
		assert(false);
	}
};
vi w;

struct Node{
	int l,r,a,m,s;
	Node(){}
	Node(int _l,int _r,int _a,int _m,int _s):
		l(_l),
		r(_r),
		a(_a),
		m(_m),
		s(_s){}
	Node(int x){
		l=r=a=m=x;
		s=1;
	}
};
Node Merge(Node x,Node y){
	if(x.s==0)return y;
	if(y.s==0)return x;
	Node res;
	res.l=max(x.l,x.a+y.l);
	res.r=max(x.r+y.a,y.r);
	res.a=x.a+y.a;
	res.m=max({x.m,y.m,x.r+y.l});
	res.s=x.s+y.s;
	return res;
}

struct Info:InfoBase{
	int en[2],al,mx,s,lz;
	Node Get(int a,int b){
		Node res(en[idx(a)],en[idx(b)],al,mx,s);
		if(s&&lz!=inf){
			res.l=lz>0?lz*s:lz;
			res.r=lz>0?lz*s:lz;
			res.a=lz*s;
			res.m=lz>0?lz*s:lz;
		}
		return res;
	}
	int GetAns(int a,int b){
		Node x(w[a]);
		Node y=Get(a,b);
		Node z(w[b]);
		Node g=Merge(x,Merge(y,z));
		return g.m;
	}
	void Join(int a,int b,int la,int lb,Info&l,int ra,int rb,Info&r,ClusterType type){
		Node g;
		REACH;
		if(type==RAKE){
			assert(a==ra);
			assert(b==rb);
			assert(lb==rb);
			
			REACH;
			g=r.Get(a,b);
		}else if(type==COMPRESS){
			assert(a==la);
			assert(lb==ra);
			assert(rb==b);
			
			REACH;
			Node x=l.Get(la,lb);
			Node y(w[lb]);
			Node z=r.Get(ra,rb);
			REACH;
			g=Merge(x,Merge(y,z));
		}
		REACH;
		en[idx(a)]=g.l;
		en[idx(b)]=g.r;
		al=g.a;
		mx=g.m;
		s=g.s;
		lz=inf;
	}
	void Create(int a,int b){
		s=0;
		lz=inf;
	}
	void Split(int a,int b,int la,int lb,Info&l,int ra,int rb,Info&r,ClusterType type){
		bool upd=lz!=inf;
		if(type==RAKE){
			assert(a==ra);
			assert(b==rb);
			assert(lb==rb);
			if(upd){
				r.lz=lz;
			}
		}else if(type==COMPRESS){
			assert(a==la);
			assert(lb==ra);
			assert(rb==b);
			if(upd){
				l.lz=lz;
				r.lz=lz;
				w[lb]=lz;
			}
		}
		if(upd)Join(a,b,la,lb,l,ra,rb,r,type);
	}
	void Destroy(int a,int b){
	}
};

signed main(){
	int n=read(),q=read();
	w=vi(n);
	REP(i,n)w[i]=read();
	TopTree<Info> tree(n);
	REP(i,n-1){
		int u=read()-1,v=read()-1;
		tree.Link(u,v);
	}
	REP(i,q){
		int t=read(),a=read()-1,b=read()-1,c=read();
		if(t==1){
			if(a==b){
				tree.Expose(a);
			}else{
				auto info=tree.Expose(a,b);
				info->lz=c;
			}
			w[a]=c;
			w[b]=c;
		}else{
			int ans;
			if(a==b){
				tree.Expose(a);
				ans=w[a];
			}else{
				auto info=tree.Expose(a,b);
				ans=info->GetAns(a,b);
			}
			print(ans);
		}
	}
}



Measured memory_bytes: 60200