Một vương quốc cổ xưa gồm \(N\) thành phố được đánh số từ \(1\) đến \(N\), các thành phố liên kết với nhau bằng \(N-1\) con đường hai chiều đảm bảo đi lại giữa hai thành phố bất kỳ. Mỗi thành phố \(u\) ban đầu thu một mức phí cầu đường là \(A[u]\).

Bob là một nhà quản lý giao thông của vương quốc và cần xử lý \(Q\) yêu cầu thuộc hai loại:

• 1 u v val: Tăng phí cầu đường của tất cả các thành phố nằm trên con đường đi ngắn nhất giữa hai thành phố \(u\) và \(v\) thêm một lượng là \(val\).
• 2 u v: Tính tổng mức phí cầu đường của tất cả các thành phố nằm trên con đường đi ngắn nhất giữa hai thành phố \(u\) và \(v\).

Hãy viết chương trình giúp Bob hoàn thành nhiệm vụ quản lý này.

Đị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 5 \cdot 10^4\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) là phí cầu đường ban đầu của các thành phố.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một con đường liên kết trực tiếp giữa hai thành phố (\(1 \le u, v \le N\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng trên.

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra tổng phí cầu đường trên con đường đi ngắn nhất.

Ví dụ

Input:

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

Output:

11
15
6