Given a tree of $n$ vertices. Vertex $i$ is assigned value $A_i$ initially. There are $q$ queries of either forms:

• 1 u v: on the simple path from $u$ to $v$, find a series of continuous vertices so that their sum is maximum possible. You can choose nothing.
• 2 u v x: change the value of every vertex on the simple path from $u$ to $v$ to $x$.

Input

• The first line contains two integers $n$ and $q$.
• The second line contains $n$ integers $A_i$.
• The next $n- 1$ line, each line contains two integers $u,v$, there is an edge connecting $u$ and $v$.
• The next $q$ lines, each representing one of the queries mentioned above.

Output

• For each query for each query of type $1$, print an integer which is the maximum sum.

Constraints

• $1 \le n, q \le 10^5$.
• $0 \le |x|, |A_i| \le 10^4$.
• $1 \le u, v \le n$.

Example

Input:

5 3
-3 -2 1 2 3
1 2
2 3
1 4
4 5
1 2 5
2 3 4 2
1 2 5

Output:

5
9