Một nông trại có ~n~ khu vườn nối với nhau bởi ~n-1~ con đường, mỗi con đường nối giữa hai khu vườn với nhau tạo thành dạng một cây đồ thị. Khi thu hoạch người ta chọn khu vườn ~1~ làm gốc của cây đồ thị. Khu vườn ~i~ đang có ~a_i~ thùng hoa quả. Ta quy ước "nhánh của khu ~u~" bao gồm khu vườn ~u~ và mọi khu vườn nằm trong cây con nhận ~u~ làm gốc.

Trong ngày, diễn ra ~q~ sự kiện thuộc hai loại:

• ~1~ ~u~ ~x~: Toàn bộ các khu vườn thuộc nhánh khu ~u~, mỗi khu thu hoạch thêm ~x~ thùng hoa quả;

• ~2~ ~u~: Tính tổng số thùng hoa quả có trong toàn bộ các khu vườn thuộc nhánh của khu ~u~.

Hãy in ra câu trả lời cho các sự kiện loại ~2~ theo đúng thứ tự dữ liệu đầu vào.

Input

• Dòng ~1~ chứa hai số nguyên ~n, q~ ~(1 \le n, q \le 2 \cdot 10^5)~ lần lượt là số khu vườn và số sự kiện diễn ra trong ngày;

• Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9, 1 \le i \le n)~;

• Tiếp theo là ~n-1~ dòng, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một con đường ~(1 \le u, v \le n; u \ne v)~. Các con đường được cho theo thứ tự bất kì và không bảo đảm ~u~ là cha của ~v~. Dữ liệu bảo đảm ~n-1~ con đường này tạo thành một cây đồ thị;

• Cuối cùng là ~q~ dòng, mỗi dòng mô tả một sự kiện thuộc một trong hai loại theo mô tả đề bài ~(1 \le u \le n; 1 \le x \le 10^4)~.

Output

Gồm nhiều dòng, mỗi dòng là một số nguyên tương ứng với câu trả lời cho sự kiện loại ~2~ theo thứ tự dữ liệu đầu vào.

Scoring

Sample Input 1

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

Sample Output 1

11
41
45
14

Notes

Nhánh của khu ~2~ gồm ~\{2,4,5\}~ với tổng số thùng là ~2+4+5=11~ thùng.

Sự kiện ~1~ tiếp theo cộng ~10~ thùng cho cả ba khu này nên tổng số thùng của nhánh trở thành ~12+14+15=41~ thùng.

Toàn nông trại khi đó có ~45~ thùng và riêng khu ~4~ có ~14~ thùng.