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 \leq i \leq 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 \leq u \leq n$$$, $$$0 \leq |c| \leq 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 \leq u, v \leq n$$$).
Help them, so you can get a portion of the treasure!
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — the number of rooms in the maze and the number of queries.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq |a_i| \leq 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 \leq s_i, t_i \leq 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.
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.
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
39 32 0
In the first query, their movement from the $$$1$$$-st to the $$$2$$$-nd room is as follows.
- $$$1 \rightarrow 5$$$ — takes $$$\max(|10 + 4|, |10 - 4|) = 14$$$ energy.
- $$$5 \rightarrow 6$$$ — takes $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ energy.
- $$$6 \rightarrow 2$$$ — takes $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ 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 \rightarrow 5$$$ — takes $$$\max(|-3 + 4|, |-3 - 4|) = 7$$$ energy.
- $$$5 \rightarrow 6$$$ — takes $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ energy.
- $$$6 \rightarrow 2$$$ — takes $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ energy.
Now, it takes $$$32$$$ energy.
