Tý cần giải bài toán sau:

Trong một công viên giải trí có \(N\) điểm tham quan được nối với nhau bởi \(N-1\) con đường (đảm bảo luôn có đường đi giữa hai điểm bất kỳ). Các điểm tham quan được đánh số từ \(1\) đến \(N\). Mỗi điểm có một chỉ số vui nhộn \(h_i\). Ban quản lý công viên thực hiện \(Q\) yêu cầu:

• 1 u val: Cập nhật chỉ số vui nhộn của điểm \(u\) thành \(val\).
• 2 u v: Tìm chỉ số vui nhộn lớn nhất trong số các điểm nằm trên đường đi từ điểm \(u\) đến điểm \(v\).

Hãy lập trình giúp ban quản lý công viên.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1, h_2, \dots, h_N\) (\(0 \le h_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả con đường nối hai điểm.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một yêu cầu.

Định dạng đầu ra

• Với mỗi yêu cầu loại 2, in ra chỉ số vui nhộn lớn nhất tìm được trên một dòng.

Ví dụ

Input:

6 4
3 7 2 5 8 1
1 2
1 3
2 4
2 5
3 6
2 4 6
1 4 10
2 4 6

Output:

8
10

Ràng buộc