Cho một cây vô hướng gồm \(N\) đỉnh, đánh số từ \(1\) tới \(N\). Mỗi đỉnh \(i\) có một giá trị nguyên \(a_i\).
Ta gọi một tập đỉnh là hợp lệ nếu không có hai đỉnh nào trong tập kề nhau trên cây. Giá trị của một tập hợp lệ là tổng các giá trị \(a_i\) của những đỉnh được chọn.
Có \(Q\) thao tác online thuộc một trong hai loại sau:

• 1 x y: gán \(a_x = y\);
• 2 u v: xét đường đi đơn từ \(u\) tới \(v\), hãy tìm giá trị lớn nhất của một tập đỉnh hợp lệ nằm hoàn toàn trên đường đi đó.
  Hãy in ra đáp án cho mỗi truy vấn loại 2. Tập rỗng được xem là hợp lệ.

Input

• Dòng đầu tiên chứa hai số nguyên \(N,Q\). \((1 \le N,Q \le 2 \times 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\). \((-10^9 \le a_i \le 10^9)\)
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một cạnh của cây. \((1 \le u,v \le N)\)
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác thuộc một trong hai dạng đã mô tả.

Output

• Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là giá trị lớn nhất có thể thu được.

Example

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

9
7

7 8
5 -2 7 3 4 -1 6
1 2
1 3
2 4
2 5
3 6
6 7
2 4 7
1 2 10
2 4 5
1 6 20
2 7 5
1 5 -100
2 4 5
2 1 7

16
10
30
10
25

Scoring

• Subtask \(1\) \((20\%\) điểm\()\): \(N,Q \le 2000\).
• Subtask \(2\) \((20\%\) điểm\()\): Cây là một đường thẳng.
• Subtask \(3\) \((20\%\) điểm\()\): Không có thao tác loại 1.
• Subtask \(4\) \((40\%\) điểm\()\): Không có ràng buộc thêm.