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