Hệ thống quản lý nội bộ gồm ~N~ máy chủ được kết nối dạng cây. Máy chủ ~i~ đang xử lý ~W_i~ luồng dữ liệu. Có ~Q~ thao tác gồm hai loại: loại ~1~ cập nhật máy chủ ~U~ lên ~X~ luồng dữ liệu; loại ~2~ yêu cầu tìm số lượng luồng dữ liệu lớn nhất trong toàn bộ cây con gốc ~U~.

Yêu cầu: Cho biết sơ đồ kết nối của ~N~ máy chủ và tải lượng ban đầu, hãy viết chương trình thực hiện ~Q~ thao tác: cập nhật số lượng dữ liệu của một máy chủ và tìm số lượng dữ liệu lớn nhất trong một cây con.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, Q~ ~(1 \le N, Q \le 2 \cdot 10^5)~. Gốc của cây là máy chủ ~1~.

• Dòng thứ hai chứa ~N~ số nguyên ~W_i~ ~(0 \le W_i \le 10^9)~ là tải lượng ban đầu của các máy chủ từ ~1~ đến ~N~.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \le u, v \le N)~ mô tả một kết nối giữa máy chủ ~u~ và máy chủ ~v~.

• ~Q~ dòng cuối cùng, mỗi dòng mô tả một truy vấn thuộc một trong hai loại sau:

  • ~1~ ~U~ ~X~: Cập nhật máy chủ ~U~ lên ~X~ luồng dữ liệu ~(1 \le U \le N, 0 \le X \le 10^9)~.

  • ~2~ ~U~: Yêu cầu tìm số lượng luồng dữ liệu lớn nhất trong toàn bộ cây con gốc ~U~ ~(1 \le U \le N)~.

Output

• Ghi ra kết quả cho các truy vấn loại ~2~.

Scoring

Sample Input 1

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

Sample Output 1

8
3
10

Notes

Hệ thống có ~5~ máy chủ, ~4~ truy vấn.

Tải lượng ban đầu: ~W = [5, 2, 8, 3, 1]~.

• Truy vấn ~1~ ~(2\ 1)~: Tìm Max cây con gốc ~1~ (gồm các máy ~1, 2, 3, 4, 5~). Các giá trị là ~\{5, 2, 8, 3, 1\}~. Lớn nhất là ~8~.

• Truy vấn ~2~ ~(2\ 2)~: Tìm Max cây con gốc ~2~ (gồm các máy ~2, 4, 5~). Các giá trị tương ứng là ~\{2, 3, 1\}~. Lớn nhất là ~3~.

• Truy vấn ~3~ ~(1\ 4\ 10)~: Cập nhật máy ~4~ thành ~10~. Mảng ~W~ lúc này trở thành: ~W = [5, 2, 8, 10, 1]~. Không in ra kết quả.

• Truy vấn ~4~ ~(2\ 2)~: Tìm Max cây con gốc ~2~ sau cập nhật. Cây con gốc ~2~ vẫn gồm ~(2, 4, 5)~, nhưng các giá trị lúc này là ~\{2, 10, 1\}~. Lớn nhất là ~10~.