human
Can you provide a Python code to find a secret treasure in a maze buried below a desert full of illusions given the following:
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


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 —...
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to find a secret treasure in a maze buried below a desert full of illusions.

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  # the root of the tree


        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...