Cho một cây $n$ đỉnh. Đỉnh $i$ được gán giá trị $A_i$. Có $q$ truy vấn thuộc một trong hai loại:

• "1 u v": trên đường đi đơn từ $u$ đến $v$, tìm một số các đỉnh liên tiếp sao cho tổng của chúng lớn nhất, hoặc không chọn đỉnh nào.
• "2 u v x": đổi giá trị của các đỉnh trên đường đi đơn từ $u$ đến $v$ thành $x$.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên $n,q$.
• Dòng thứ hai gồm $n$ số nguyên $A_i$
• $n-1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u,v$, có một cạnh nối $u$ và $v$.
• $q$ dòng tiếp theo, mỗi dòng gồm một truy vấn nêu trên.

Dữ liệu ra

• Với mỗi truy vấn thuộc loại $1$, in ra một số nguyên là tổng lớn nhất.

Điều kiện

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

Input 1

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 1

5
9

Input 2

7 7
3 -2 3 1 -3 3 -3
1 2
1 3
1 4
1 6
2 5
2 7
2 5 1 0
2 4 6 -2
1 3 2 
2 4 1 -5
1 4 5 
2 1 2 2
1 4 5

Output 2

3
0
4