Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.

The map of the labyrinth forms a tree with n rooms numbered from 1 to n and n - 1 tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.

The i-th room (1 ≤ i ≤ n) has a_i illusion rate. To go from the x-th room to the y-th room, there must exist a tunnel between x and y, and it takes max(|a_x + a_y|, |a_x - a_y|) energy. |z| denotes the absolute value of z.

To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask q queries.

There are two types of queries to be done:

  * 1\ u\ c — The illusion rate of the x-th room is changed to c (1 ≤ u ≤ n, 0 ≤ |c| ≤ 10^9). 
  * 2\ u\ v — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room v if they are initially at room u (1 ≤ u, v ≤ n). 



Help them, so you can get a portion of the treasure!

Input

The first line contains two integers n and q (2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5) — the number of rooms in the maze and the number of queries.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ |a_i| ≤ 10^9) — inital illusion rate of each room.

The i-th of the next n-1 lines contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ n), meaning there is a tunnel connecting s_i-th room and t_i-th room. The given edges form a tree.

The next q lines contain the query as described. The given queries are valid.

Output

For each type 2 query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.

Example

Input


6 4
10 -9 2 -1 4 -6
1 5
5 4
5 6
6 2
6 3
2 1 2
1 1 -3
2 1 2
2 3 3


Output


39
32
0

Note

<image>

In the first query, their movement from the 1-st to the 2-nd room is as follows.

  * 1 → 5 — takes max(|10 + 4|, |10 - 4|) = 14 energy. 
  * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 
  * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 

In total, it takes 39 energy.

In the second query, the illusion rate of the 1-st room changes from 10 to -3.

In the third query, their movement from the 1-st to the 2-nd room is as follows.

  * 1 → 5 — takes max(|-3 + 4|, |-3 - 4|) = 7 energy. 
  * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 
  * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 



Now, it takes 32 energy.
#include<bits/stdc++.h>
#define il inline
#define re register
#define ll long long
#define lowbit(x) ((x)&(~(x)+1))
#define iL (1<<20)
#define TEM template<class T>il void
#define Write(x,LC) write((x)),*iter++=LC
#define flush() fwrite(Out,1,iter-Out,stdout),iter=Out
#define gc() ((iS==iT)?(iT=(iS=ibuf)+fread(ibuf,1,iL,stdin),(iS==iT)?EOF:*iS++):*iS++)
using namespace std;
namespace IO{
	char ibuf[iL],*iS=ibuf+iL,*iT=ibuf+iL,Out[iL],*iter=Out;
	TEM readneg(re T &x){re char c;re bool f;for(f=false,c=gc();!isdigit(c);f|=c=='-',c=gc());for(x=0;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=gc());if(f)x=~x+1;}
	TEM read(re T &x){re char c;for(c=gc();!isdigit(c);c=gc());for(x=0;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=gc());}
	TEM write(re T x){re T c[35],l;for(l=0;!l||x;c[l++]=x%10,x/=10);for(;l;*iter++=c[--l]+'0');flush();}
}
using namespace IO;
#define MAXN 100005
struct Edge{int next,to;}E[MAXN<<1];int head[MAXN],cnt;
il void AddE(int x,int y){E[++cnt].next=head[x],E[cnt].to=y,head[x]=cnt;}
int n,m,val[MAXN],V[MAXN];
int fa[MAXN],son[MAXN],dep[MAXN],top[MAXN],sz[MAXN],dfn[MAXN],DFN;
void dfs1(int x,int fat){
	dep[x]=dep[fa[x]=fat]+1,sz[x]=1;
	for(re int i=head[x];i;i=E[i].next){
		if(E[i].to^fat){
			dfs1(E[i].to,x),sz[x]+=sz[E[i].to];
			if(sz[son[x]]<sz[E[i].to])son[x]=E[i].to;
		}
	}
}
il int Getval(int x,int y){return max(abs(x-y),abs(x+y));}
void dfs2(int x,int fat){
	V[dfn[x]=++DFN]=Getval(val[x],val[fa[x]]),
	top[x]=fat;if(son[x])dfs2(son[x],fat);
	for(re int i=head[x];i;i=E[i].next)if(E[i].to^fa[x]&&E[i].to^son[x])dfs2(E[i].to,E[i].to);
}
ll sum[MAXN];
il void Add(int x,int w){for(;x<=n;sum[x]+=w,x+=lowbit(x));}
il ll Qry(int x){re ll ans=0;for(;x;ans+=sum[x],x^=lowbit(x));return ans;}
il void Modify(int x,int w){
	val[x]=w;re int W=Getval(val[x],val[fa[x]]);
	Add(dfn[x],W-V[dfn[x]]),V[dfn[x]]=W;
	for(re int i=head[x];i;i=E[i].next){
		re int y=E[i].to;
		if(y^fa[x])W=Getval(val[x],val[y]),Add(dfn[y],W-V[dfn[y]]),V[dfn[y]]=W;
	}
}
il ll Query(int x,int y){
	re ll ans=0;
	for(;top[x]^top[y];dep[top[x]]<dep[top[y]]?x^=y^=x^=y:0,ans+=Qry(dfn[x])-Qry(dfn[top[x]]),x=fa[top[x]]);
	dep[x]>dep[y]?x^=y^=x^=y:0,ans+=Qry(dfn[y])-Qry(dfn[x]);
	return ans;
}
int main(){
	read(n),read(m);
	for(re int i=1;i<=n;++i)readneg(val[i]);
	for(re int i=1,x,y;i<n;++i)read(x),read(y),AddE(x,y),AddE(y,x);
	dfs1(1,0),dfs2(1,0);for(re int i=1;i<=n;++i)Add(i,V[i]);
	for(re int _=0,ty,x,y;_<m;++_){
		read(ty),read(x),readneg(y);
		if(ty==1)Modify(x,y);
		else Write(Query(x,y),'\n');
	}
}