Hưng thịnh

Đất nước Z có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) và được nối với nhau bởi \(n - 1\) con đường để đảm bảo đi lại giữa hai thành phố bất kỳ. Mức độ phát triển của thành phố \(i\ (1 \le i \le n)\) là \(p_i\). Chính phủ thực hiện một dãy gồm \(q\) các công việc thuộc một trong hai loại sau:

• Loại \(1\) có dạng \(1\ i\ x\), nghĩa là đầu tư vào thành phố \(i\ (1 \le i \le n)\) để tăng mức độ phát triển của thành phố \(i\) thêm \(2x\), mức độ phát triển của các thành phố liền kề \(i\) cũng được tăng thêm \(x\).

• Loại \(2\) có dạng \(2\ i\), nghĩa là tính độ hưng thịnh của cụm các thành phố khi lấy \(i\) làm trung tâm, giá trị này được tính bằng mức độ phát triển của thành phố \(i\) và tất cả các thành phố kề \(i\).

Yêu cầu: Với mỗi công việc loại \(2\) đưa ra giá trị cần tính.

Input

• Dòng đầu chứa hai số nguyên \(n, q\ (n \le 3 \times 10^5; q \le 3 \times n)\).
• Dòng tiếp theo là \(n\) số nguyên không âm \(p_1, p_2, \ldots, p_n\ (p_i \le 10^9)\).
• Tiếp theo là \(n - 1\) dòng, mỗi dòng là một cặp số nguyên \(u, v\) mô tả có con đường nối thành phố \(u\) với thành phố \(v\).
• Tiếp theo là \(q\) dòng, mỗi dòng mô tả công việc mà chính phủ thực hiện.

Output

• Với mỗi công việc loại \(2\), đưa ra giá trị cần tính.

Example

3 5
0 0 0
1 2
2 3
1 1 1
1 2 2
2 1
2 2
2 3

9
11
7