Có một cây (đồ thị vô hướng liên thông không có chu trình) gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Mỗi đỉnh có một trọng số.

Hãy viết chương trình thực hiện hai loại truy vấn sau:

• 1 u v: Tìm tổng đoạn con liên tiếp lớn nhất (có thể rỗng, vì vậy kết quả không âm, lớn hơn hoặc bằng $0$) trên đường đi từ $u$ đến $v$ và in ra.
• 2 u v w: Thay đổi trọng số của tất cả các đỉnh trên đường đi từ $u$ đến $v$ thành $w$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100{,}000$).

Dòng thứ hai chứa trọng số của các đỉnh theo thứ tự từ đỉnh $1$ đến đỉnh $N$.

Dòng thứ ba đến dòng thứ $N-1$: mỗi dòng chứa hai số nguyên $u$ và $v$ là hai đỉnh đầu mút của cạnh thứ $i$.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

$M$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.

Trọng số của các đỉnh là số nguyên có giá trị tuyệt đối không vượt quá $10{,}000$.

Dữ liệu ra

Với mỗi truy vấn loại 1, in ra kết quả trên một dòng, theo đúng thứ tự.

Ví dụ

Đầu vào

5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5

Đầu ra

5
9