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.

Difficulty: HARD
Tags: Tree algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
INF = float('inf')

class lca_binarylift(object):

	def __init__(self, neigh):
		set_root = 0
		self.n = len(neigh)
		self.parents = [[] for i in range(self.n)]
		self.depth = [-1] * self.n
		self.depth[set_root] = 0
		self.parents[set_root].append(-1)
		queue = deque([[set_root, 0]])
		while queue:
			(index, d) = queue.popleft()
			for nextindex in neigh[index]:
				if self.depth[nextindex] >= 0:
					continue
				self.depth[nextindex] = d + 1
				self.parents[nextindex].append(index)
				queue.append([nextindex, d + 1])
		self.maxdepth = max(self.depth)
		k = 1
		while True:
			op = 0
			for i in range(self.n):
				if len(self.parents[i]) == k and self.parents[i][k - 1] >= 0:
					nextl = len(self.parents[self.parents[i][k - 1]])
					actual = min(nextl - 1, k - 1)
					self.parents[i].append(self.parents[self.parents[i][k - 1]][actual])
					op += 1
			if op == 0:
				break
			k += 1

	def move(self, index, step):
		if step > self.depth[index]:
			return -1
		i = 0
		while step:
			if step & 1:
				index = self.parents[index][i]
			step = step >> 1
			i += 1
		return index

	def query(self, index1, index2):
		if self.depth[index1] >= self.depth[index2]:
			index1 = self.move(index1, self.depth[index1] - self.depth[index2])
		else:
			index2 = self.move(index2, self.depth[index2] - self.depth[index1])
		front = 0
		rear = self.maxdepth + 1
		while front < rear:
			mid = (front + rear) // 2
			if self.move(index1, mid) == self.move(index2, mid):
				rear = mid
			else:
				front = mid + 1
		return self.move(index1, front)

class fenwick(object):

	def __init__(self, n):
		self.n = n
		self.cul = [0] * n

	def update(self, index, diff):
		i = index
		while i < self.n:
			self.cul[i] += diff
			i += i + 1 & -i - 1

	def getaccu(self, index):
		output = 0
		i = index
		while i >= 0:
			output += self.cul[i]
			i -= i + 1 & -i - 1
		return output

	def query(self, front, rear):
		return self.getaccu(rear) - self.getaccu(front - 1)

class heavy_light(object):

	def __init__(self, n, neigh):
		self.n = n
		self.children = [[] for i in range(n)]
		self.neigh = neigh
		self.parent = [-1] * n
		self.ancestor = [-1] * n
		self.rename = [-1] * n
		self.totnum = [0] * n
		self.maxchild = [-1] * n
		self.renameindex()

	def getchild(self):
		visited = [False] * self.n
		queue = deque()
		queue.append(0)
		visited[0] = True
		seq = [0]
		while queue:
			index = queue.popleft()
			for nextindex in self.neigh[index]:
				if visited[nextindex]:
					continue
				visited[nextindex] = True
				queue.append(nextindex)
				self.children[index].append(nextindex)
				self.parent[nextindex] = index
				seq.append(nextindex)
		for index in seq[::-1]:
			maxcnum = 0
			for ele in self.children[index]:
				self.totnum[index] += self.totnum[ele]
				if self.totnum[ele] > maxcnum:
					maxcnum = self.totnum[ele]
					self.maxchild[index] = ele
			self.totnum[index] += 1

	def renameindex(self):
		self.getchild()
		stack = [(0, 0)]
		currindex = 0
		while stack:
			(index, ances) = stack.pop()
			for ele in self.children[index]:
				if ele == self.maxchild[index]:
					continue
				stack.append((ele, ele))
			self.ancestor[index] = ances
			self.rename[index] = currindex
			if self.maxchild[index] > 0:
				stack.append((self.maxchild[index], ances))
			currindex += 1

	def getpath(self, index):
		output = []
		ori = index
		while index >= 0:
			front = self.rename[self.ancestor[index]]
			rear = self.rename[index]
			output.append([front, rear])
			index = self.parent[self.ancestor[index]]
		return output[::-1]
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
	arr[i] = abs(arr[i])
neigh = [[] for i in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	neigh[u - 1].append(v - 1)
	neigh[v - 1].append(u - 1)
new = heavy_light(n, neigh)
lca = lca_binarylift(neigh)
fen = fenwick(n)
for i in range(n):
	index = new.rename[i]
	fen.update(index, arr[i])
for _ in range(q):
	(op, a, b) = map(int, input().split())
	if op == 1:
		i = a - 1
		index = new.rename[i]
		diff = abs(b) - arr[i]
		arr[i] = abs(b)
		fen.update(index, diff)
	else:
		(front, rear) = (a - 1, b - 1)
		oricommon = lca.query(a - 1, b - 1)
		to_rear = new.getpath(b - 1)
		to_front = new.getpath(a - 1)
		to_common = new.getpath(oricommon)
		output = 0
		for ele in to_rear:
			output += fen.query(ele[0], ele[1])
		for ele in to_front:
			output += fen.query(ele[0], ele[1])
		for ele in to_common:
			output -= 2 * fen.query(ele[0], ele[1])
		output += arr[oricommon]
		output = 2 * output - arr[front] - arr[rear]
		print(output)