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