Electronic Fireworks

A party organizer, Old V, has brought an advanced "electronic fireworks" machine, dubbed Fire \(\textbf{Tree}\) and Silver Flowers. The device is based on a tree with \(n\) nodes, where each node \(u\) has a brilliance value \(l_u\) representing the dazzling style of the firework at that node.

The tree is undirected and connected (i.e. a tree) with \(n\) nodes. There will be \(q\) operations performed on the tree. For any two nodes \(u\) and \(v\), let \(P(u,v)\) denote the set of nodes on the unique simple path from \(u\) to \(v\) (including both \(u\) and \(v\)). There are two types of operations:

1. Update Operation: Given \(u\), \(v\) and an integer \(k\), update the brilliance value of every node \(w\) which either lies in \(P(u,v)\) or has at least one adjacent node in \(P(u,v)\). That is, set \(l_w = k\) for every such node.
2. Query Operation: Given \(u\) and \(v\), form a sequence \(S\) as follows. First, consider the simple path \(P(u,v)\) = \(\{w_1, w_2, \dots, w_m\}\) from \(u = w_1\) to \(v = w_m\). For each node \(w_i\) on this path (in order):
   1. Append \(l_{w_i}\) to \(S\).
   2. Then, consider all neighbors of \(w_i\) sorted in increasing order of their indices. For every neighbor \(x\) that is not in \(P(u,v)\), append \(l_x\) to \(S\).
   After constructing \(S\), the system will ignite a contiguous subsegment of \(S\) whose sum of brilliance is maximized (an empty subsegment is allowed and has sum 0). Report this maximum subsegment sum.

You are required to process all \(q\) operations in order. For each query (type 1) operation, output the maximum contiguous subsegment sum of the generated sequence \(S\>.

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of nodes and the number of operations, respectively.

The second line contains \(n\) integers \(l_1, l_2, \dots, l_n\) which represent the initial brilliance values of the nodes.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), denoting an undirected edge connecting nodes \(u\) and \(v\) in the tree.

Then \(q\) lines follow, each representing an operation. Each line begins with an integer representing the operation type. If the operation is of type 0, the line contains three integers: 0 u v k. If the operation is of type 1, the line contains two integers: 1 u v.

outputFormat

For each query (type 1) operation, output a single line containing the maximum contiguous subsegment sum computed from the sequence \(S\). (If there are no nodes in the subsegment, output 0.)

sample

5 3
1 2 3 4 5
1 2
2 3
3 4
3 5
1 1 5
0 2 3 10
1 1 5

15
50